Ich hab das nochmal geprüft.
Mein Installationsprogramm ist ein "addon" für ein bereits installiertes Tool: Hello World. Das Setup von Hello World fügt einen den Startmenü Eintrag im Ordner <All Users> hinzu. (d.h. <All Users>\Startmenü\Hello World\start.lnk)
SHGetSpecialFolderPath(Form1.Handle, b, CSIDL_PROGRAMS, True);
liefert mir das Startmenü im Ordner <Rechnername>. D.h. mein Programm muss im Ordner <Rechnername> nochmal den Ordner "Hello World" anlegen und darin dann den zusätzlichen Link. Ist zwar doppelt gemoppelt aber müsste so gehen.