Yes, you can define a custom menu entry for RMB (CommandBars("Component Popup").Controls.Add...)
I'm not sure if you can make the sub-menu dynamically, it would be easier to have a fixed set of options (i.e. horizontal / vertical). You can use the UpdateMethod property to dynamically enable/disable the submenu entries based on whether the symbols exist in the library.
Then in the menu handler code when you know the symbol you want, call ChangeComponentPreserveRefdes. Use "<Selected Components>" as the first argument.
Depending on how different the symbols are, you may end up losing some connections, so you may want to query to the component connections before replacing the symbol, then repair any disconnections after the symbol is replaced.