Adding the "secondary" shortcuts to the button tooltips is easy, but adding to the main-menu is more difficult.

How about just changing the "primary" shortcut to the most useable/obvious/one-key shortcut so they appear in the button tooltips ?
Such as "g" for gradient  instead of Ctrl+F1.