What are good options for Windows GUI toolkits for a Perl program?

With respect to "perlishness" of the interface, I'd suggest plain old Tk. Unfortunately, it looks quite antiquated and non-win32-ish.

If you want native widgets, I think your best shots are using the native Windows GUI via Win32::GUI or Wx. I have no experience with Win32::GUI, but Wx is quite nice. It does, however, have a rather steep learning curve and the interface isn't very "perlish". The C++ roots show a little bit (for better or worse).

There are a few Tk-replacements that are actually thin wrappers around Tcl/Tk (I think Tcl::Tk and Tkx). They look more modern than Perl/Tk, but I have no hands-on experience with these either. If you're developing for Windows only, have a look at ActivePerl which comes with (I think) Tkx. Their ppm4 package manager is written using it and looks pretty nice!

There are a number of options listed in perlfaq3 and some additional ones that aren't. I'm only familiar with the Tk-based ones.

Perl/Tk has the most "perlish" interface but it hasn't been updated to take advantage of tile (native/themed widget) support in the current version of Tk (and probably never will be). Tkx uses a different bridge to Tk. It allows access to everything in Tk (and it's faster, too) but the syntax is less perlish. Tkx is designed to be a thin wrapper over Tk; you have to consult the Tk documentation for most things and translate for using it from Perl. The Tcl/Tk module uses the same bridge as Tkx but supports a syntax that's mostly the same as Perl/Tk.

Whether or not you need to compile anything depends on which version of Perl you use. If you use Strawberry Perl you'll probably have to compile something no matter what toolkit you choose. ActivePerl distributions have included Tkx since sometime in the 5.8.x cycle and stopped bundling Tk as of 5.10, although it's still available via PPM. Tcl/Tk is available from CPAN but I haven't been able to get it to work with the Tk library that comes bundled with ActivePerl; you may need to install Tcl separately to use it.

Personally, I used to use Perl/Tk but now use Tkx.

While Tk and Qt are also available (more general frameworks originally intended for other languages, on which you can also use Perl), and Tk probably most popular as it's been around longest, Win32::GUI would seem to meet your requirements best. If you like WISIWYG GUI designers, you could use Loft on top of Win32::GUI, but you don't have to if you'd rather do everything programmatically.