Вы можете попытаться изменить Directory = 'ProgramMenuDir' на Directory = 'ProgramMenuFolder', в противном случае создайте отдельный компонент ярлыков;
<Directory Id="TARGETDIR" Name="SourceDir">
<Directory Id="ProgramMenuFolder">
<Component Id="Shortcuts" Guid="{}">
<Shortcut Id='myShortcut' Name='Prog' Icon='MyIcon.exe' IconIndex='0' Directory='ProgramMenuFolder' WorkingDirectory='INSTALLDIR' Target="[INSTALLDIR]Prog.exe" />
<RegistryValue Root='HKCU' Key='SOFTWARE\prog\prog' Type='string' Value='1' KeyPath='yes' />
</Component>
</Directory>
<!-- other files -->
</Directory>