Then don't have your start menu executables want to start with bloody administrator level permissions.
P.S.
I seem to be able to create shortcuts into the start menu without UAC with explorer. I.E. your issue is not with UAC.
OK, find a folder with an exe in it that you want to have a shortcut to. Open Explorer Window there. Find a Start Menu folder that you want it to be put in. Open Explorer Window there.
Now, hold your right mouse button down on the exe, drag it to the Start Menu folder, and from the list, click "Create Shortcut". Been doing that nifty little trick since Windows '95. Except now it doesn't work.
Wait a minute. OK, yeah, it's not UAC to blame here, but something within Windows is basically saying I'm not allowed to create shortcuts there. The message I get is the same one I would get if I tried to make a shortcut to a .exe in, say, My Computer (Where the list of drives goes) or the Control Panel. Problem is, it's just the generic location for the Start Menu.
Sorry, mis-labeled the topic. It's not UAC.

EDIT: OK maybe I found it. Just had a thought whilst re-reading this.
This is the Start Menu location:
C:\Users\JP\AppData\Roaming\Microsoft\Windows\Start Menu
This is the Start Menu location that GOG used:
C:\ProgramData\Microsoft\Windows\Start Menu\Programs\GOG.com\Freespace 2
Apparently I'm not allowed to write to location #2 unless I'm using an elevated cmd prompt.

a) Why are there two locations (must be to make things simple, right?)
b) Why am I not allowed to create shortcuts via my method described above in the ProgramData location??? Using an Elevated Windows Explorer window? (Yes I just verified that I can create shortcuts in the AppData location using my method and I don't need elevated anything.)