I installed Office365 over my old Office 2013 installation. O365 removes Office 2013, but I noticed after I was done (and had rebooted) when I pressed the start menu and started typing (for example) “Word” the only thing that came up in search results was “Word 2013”. The icon did nothing, and I couldn’t find the Office 2016 applications that way. They were listed in the start menu, but I like to be able to quickly type the name, hit enter, and launch the application.
I tried every solution I could find online – registry edits, stopping and restarting services, rebuilding the Windows search index, powershell commands – and nothing worked.
Finally I created another local user account on the system and that one worked fine. So I concluded something was broken in my user profile. I logged in as the built-in administrator account, backed up all my files from my previous user profile, deleted it, recreated it, and everything works fine now.
So, if your Windows start menu is acting weird, try creating a new profile and see if that fixes it.