As the problem persisted I would have decided to delete all the shortcuts in the desktop and start menu.
I would have adding shortcuts to the start menu only by right-clicking the .exe files and selecting "Pin to Start Menu". By doing this I would be able to have shortcuts to numerous applications in the start menu, although if the problem persisted for the desktop shortcuts when I restarted the computer I would have looked for other options.
Im guessing you issues persisted.