Former examples I have seen, only dealt with adding to an existing menu.

-
possible duplicate of How make AddMenuCommands work in an init.m –  Szabolcs May 30 '12 at 16:25
Or maybe this one: mathematica.stackexchange.com/q/907/12 –  Szabolcs May 30 '12 at 16:26
I was too quick to mark as duplicate, I am sorry. You are right that the other examples add to existing menus, and don't add a new menu. –  Szabolcs May 30 '12 at 21:00
AFAIK you can only do this by manually altering the MenuSetup.tr file -- but will be interested in other methods are available. –  Mike Honeychurch May 30 '12 at 23:31
@Szabolcs No problem :-) –  magma May 31 '12 at 0:48

You can't add an entirely new menu using AddMenuCommands. We have it from John Fultz here:

(I trust I've not taken that out of context.)

-
I feared that. Still..is it possible to force MMA to read and apply a new MenuSetup.tr file during a session? maybe by restarting the fron-end? –  magma May 31 '12 at 0:52

You can change the Mathematica menu in the way you desire by editing the MenuSetup.tr file, and restarting Mathematica. I make this change each time I get a new version of Mathematica.

Of course, this isn't ideal, because it involves making a permanent change to the system, but it does work - just follow the style of the rest of the file.

Be careful to back up the original file, and make your changes a little at a time, because Mathematica isn't very informative if you get the syntax wrong. Don't use operators in this file - last time I tried, they failed.

-
Thank you David, this was known, but the real point is: can we do this programmatically? Can a user-package do this and then perhaps programmatically restart the fron-end so that the new Menu takes effect? You can see from my comment above in Degnen's answer and in the question text that the real challenge lies in doing this programmatically. –  magma Aug 21 '14 at 9:45