I post this as a tentative answer. Votes will tell whether it works for many people or not. I had the same problem: Windows 10 search would not show icons for pre-installed Windows apps such as Microsoft Store, Calculator, ..., while the icons where showing fine in the start menu. All other icons on my system were fine.
I had tried @Tom21487's answer before (I had set all performance options to "best appearance", and rebooted), with no luck. I have also tried to delete caches like here, including in addition
"%localappdata%\Microsoft\Windows\Explorer\thumbcache*", with no luck either. I am not saying these may not have been part of the solution, but they alone did not fix it.
Then, I stumbled upon this June 12, 2018 post (on page 5) by Leeron JVC:
Good day! Fortunately, I fixed mine changing the icon scale (Mine was
at recommended 100% so whatever yours are I hope will apply to what I
did too) from 100% to 125%. It didn't fix it so I just changed it
back to 100%, and by my surprise, it was fixed!
So I should add that I am on a laptop computer with 150% recommended element size, which I tend to set to 125% while on a laptop, and Windows 10 is smart enough to set it to 100% for an external display. Anyway, I set the element size to 100%, and it worked - 150%, worked - back to 125%, still worked.
Here's Microsoft's official instructions on how to do this:
In Windows: Select the Start menu, then type change display settings in the search box on the taskbar. From the list of results, choose Change display settings and then choose the size under Scale and layout.
Finally, this "fix" survived my restoring performance settings to "best performance" (except font smoothing and drop shadows) and a reboot.