As previously mentioned, if this happens to random icons there's a very good chance files have been removed from the C:\Windows\Installer folder. Usually by using a third party cleaner. CCleaner followed by Glary Utilities are two of the gentler cleaners that I've used/use.
Worth checking first:
Right click on the offending icon and check its properties. Where does it say to "Start In" and "Target". Although these should be right as the shortcuts work.
Click the change icon button and make note of the initial opening file address. If it's third party software and it opens with shell32, the original icon source file is missing. Do the repair.
If you click on the offending programs in Control Panel/Programs and Features do you get an option to repair? If not try running the programs installer again (without uninstalling) to repair the set up. If it is down to missing files in the installer folder it will replace them.