I hardly use the Windows or Open Shell Menu's search function to search programs. I also don't use any Microsoft Store Apps, probably the only one is the Weather and News on the task bar.
The best of Open Shell Menu is that it let you customize the menu. You can also pin about anything to the menu. If something can't be pinned directly, control panel items for example, I'll create a shortcut, pin the shortcut to the menu, then delete the shortcut.
If I need to search files or folders, I'll use
Everything.
If I need search something on internet, I'll use Chrome.