If hands-on-keyboard-and-mouse (HOKAM?) is important, I would suggest looking at the digital content creation apps like Blender and Maya context menus and pie menus for inspiration.

I know with my use of Emacs, I'd probably use or configure it like a fancy which-key: use the mouse to navigate / filter the available choices but then use the keyboard for final selection.