• A 'visual' Perl distribution - a downloadable Perl installation with an integrated IDE. There are two open source Perl IDEs that I know of offhand: OpenPerlIDE and Eclipse with EPIC (I make no comment about the relative merits of either). Bundle one of these with a compiled Perl for Windows, put it in a nice installer package, and that should make things much easier for newbies to get started. You could even include a GUI builder, there are a few around if you look carefully.
• As you've suggested, whizzier GUI libraries, easier to use might help. I've gone on at some length about the relative merits of different GUI libraries before Re: GUI toolkit choice, and am currently working on an abstraction module to try and make Tk coding in OO paradigm easier, based on the stuff I wrote for TPR last year. But if Tk doesn't look whizzy enough, why not get involved and try improving it. Or as Jettero has said, writing docs for Wx (although TBH, once you get used to it, the existing docs are fine - maybe a meta doc helping the newbie get used to using the C docs?)
• Write something for automagicmikes perltv project
• No doubt many others

On the GUI question, personally I have reservations about the 'if you want to write a GUI, use something else' argument. I find most of the GUI facilities in Java even more grotesque and work intensive than Tk. Perl is a good enough general purpose language that I rarely have occasion to use anything else - relegating it to nothing but text processing and glue is IMO doing a huge disservice to Perl and all the people who've put massive amounts of work into facilities like Tk, Wx, Prima etc.

On a really general point for anyone reading this and thinking 'yeah, that might be good if someone did that': it can be difficult to get your head fully around the grassroots paradigm - I know I struggled with it quite recently. To try and make it clearer: If something needs doing, get on and do it. If you don't feel you're competent to do it, do it anyway - you're almost certainly wrong. Once something is underway if it looks useful people will help, and it can always be cleaned up and improved on later.