To change the icon of a folder in %AppData%\Microsoft\Windows\Start Menu\Programs, right click it -> Properties -> Customize tab -> Change the icon.
Then open %appdata%\ClassicShell and delete the DataCache.db which will force the Start Menu to rebuild the cached icons.
To change the icon of a folder in %ProgramData%\Microsoft\Windows\Start Menu\Programs is tricky. Either the file manager you are using has to opened as administrator or the Properties dialog must be opened as administrator. But the problem is Windows File Explorer in Windows 7/8 cannot be opened as administrator - it doesn't really elevate because of a DCOM restriction Microsoft put in the registry.
Explorer++ (
http://explorerplusplus.com/) is a good free alternative for such operations. Open Explorer++ as admin and open the Properties of any folder inside %ProgramData%\Microsoft\Windows\Start Menu\Programs. The Properties will also open elevated. Change the icon. Then delete the Classic Shell DataCache.db to refresh it.