To add entries to the All Programs portion, merely include a shortcut under the folder %AllUserProfile%\Microsoft\Start Menu\Programs.
You can use the SpecialFolder object in VBScript.
Not sure how to do it in Powershell, but this is it in Javascript:
var shell = WScript.CreateObject("WScript.Shell");
var allUserProfilePath = shell.SpecialFolders("CommonPrograms");
var myShortcut = shell.CreateShortcut(allUserProfilePath + "\\myShortcut.lnk");
myShortcut.TargetPath = "c:\\My Programs Path";
myShortcut.WorkingDirectory = "c:\\Blah";
myShortcut.WindowStyle = 4;
myShortcut.Save();
The translation to VB is straight forward
Dim shell
Set shell = WScript.CreateObject("WScript.Shell")
Dim allUserProfilePath
Set allUserProfilePath = shell.SpecialFolders("CommonPrograms")
Dim myShortcut
Set myShortcut = shell.CreateShortcut(allUserProfilePath + "\myShortcut.lnk")
myShortcut.TargetPath = "c:\My Programs Path"
myShortcut.WorkingDirectory = "c:\Blah"
myShortcut.WindowStyle = 4
myShortcut.Save()