I know that we had the exact same issue with Windows 7 but this is a Windows setting (at leats it was then).
If you go to task manager and start menu properties and then go to the tab start menu and select Customize you get advanced options for the start menu.
Then theres an option there that says "Search Programs and Control Panel". Maybe there is soemthing like that in W10??
Maybe this link helps??
Windows 10 Search can't find ANY applications. Even calculator - Super User