Windows search bar will only open trusted windows-store apps

Question

Before the recent Windows Creator update my searchbar was already misfunctioning and not even finding programs at all (just as background if needed).
Since the update the searchbar now finds programs like paint and the new Paint 3D again, however only those that have the line "Trusted Windows-Store App" (free translation from German) beneath them can be opened from the searchbar.
In the example with Paint, that only would be Paint 3D which I can open without any problem.
Any other program that is found (in this case the normal mspaint) and does not have this line, cannot be opened from the searchbar for some reason. When clicking on the item simply nothing happens. The color change of the clicking animation is there but nothing else. The search does not close, the program does not start. This includes programs I installed but windows default installations like Paint and the Services as well.

Any ideas where the problem might be and how to solve it are much appreciated!

Note: I do not have Cortana enabled.

Answer 1

On my 15063.250 machine(Enterprise edition), search function is fine, I can search desktop programs and store apps. As you said, after typing Paint, both of Paint and Paint 3D appears.

So, please run Cortana troubleshooter at first.

If no help, try to create a new admin account to test again.