In InnoSetup there are two constants: {commonstartmenu} and {userstartmenu}, which are expanded as "C:\ProgramData\Microsoft\Windows\Start Menu" and "C:\Users\Username\AppData\Roaming\Microsoft\Windows\Start Menu" respectively on my PC under Windows 7.
Can I simply add "\Programs" string to them to get the path of the All Programs folder of common and user Start Menu? Is it guaranteed that All Programs folder of Start Menu is named "\Programs"? If no, how can I obtain its name?
No, you cannot assume that it is named "Programs".
{commonprograms} is the correct constant to use if you want to refer to "Programs" / "All Programs" directly.
However if you want to install more than one shortcut then it is better to use {group} and DefaultGroupName as RobeN suggested.