I've written several apps in Visual C++ that create right-click menus, so I know this shouldn't be an impossible task. There is a known issue with getting menus to appear that is addressed in this MSDN article.
As far as I know, you can have the popup menu load an existing resource, which seems less likely with Win32::GUI, or have it create a menu on the fly. I'd offer some code, but I haven't tried Win32::GUI yet and my VC++ code is at home. Hopefully the MSDN article will give you a push in the right direction!

Guildenstern
Negaterd character class uber alles!