Hi there, felixfreiberger. You may want to run through this tutorial: Apps and Tiles Not Working or Responding: Fix in Windows 8
Unluckily, nothing that applies to my situation did help.
(I'm not going to refresh my PC.)
a file was moved, deleted or somehow corrupted..
No corruption found in that?
Quite honestly I've never seen this before, especially when desktop apps icons show. Weird indeed.
Have you made changes to your system lately? new app(s) or anything?
Did you try a Restore Point?