From your "Start" menu, expand the program folder you want the icon to be changed, right click on the file that would normally start the program and select "Properties", from there select "Change Icon"
After you've changed the icon and still using a "Hot Key" to start the program, you're not going to see the new icon unless you "Pin to Taskbar" or "Pin to Start Menu"
Hope this helped