It doesn't take much code to add a command to a shortcut menu in Excel, but the menu objects have strange names so it's not intuitive, to me at least. The trickiest part is just sorting out how it's supposed to work, because it seems like it should be different from adding buttons to toolbars, but it really looks like that's what you're doing.
The code is all posted in this post on the VSTO team blog.
Thanks to McLean Schofield, programmer/writer and 3-star forum answer person, for this code example!