Este pode funcionar, mas você terá que iniciar o programa a partir do Script e os ícones estarão à direita.
script.bat
script.vbs prog.exe link
script.vbs
prog = WScript.Arguments.Item(0)
lk = WScript.Arguments.Item(1)
Set oWS = WScript.CreateObject("WScript.Shell")
sLinkFile = "%userprofile%"\start menu\programs\"+prog+".lnk"
Set oLink = oWS.CreateShortcut(sLinkFile)
oLink.TargetPath = lk
oLink.Save