Enterbrain's official recommendation is that you create a shortcut to the Game.exe file and you change the icon on the shortcut. However, while changing the Game.exe's icon IS against the EULA, this is one change that is tolerated by the company.
Right-clicking your exe and changing the icon in Properties is NOT the approach to use. That would change the icon on YOUR computer, but everyone else who downloads your game would still get the default icon.
ResHacker is pretty easy to use for this purpose.