It works! I think my (and perhaps Andrea's) mistake was assuming that the PDF::API2 "core fonts" were the same as the standard TrueType fonts of the same name -- in my case, the version of Times New Roman in the Windows Fonts folder. When I changed your font line in the script above to this:

my $font = $pdf->ttfont('C:/Windows/Fonts/times.ttf');

I got the appropriate Unicode text in my PDF, in Times New Roman. The standard TrueType versions of Times New Roman, Verdana, and other fonts that come with Windows and probably other systems do support at least the basic Greek character set. That was why I assumed that the core fonts "should" support Greek. Thanks for your help!

Thanks, too, for the recommendation for the DejaVu fonts. They seem like nice ones! I am kind of a font hoarder, especially for useful Unicode ones. For the extended Greek character set, diacritics and such, I also like the New Athena fonts (one of which supports the inverted breve circumflex, as opposed to the tilde circumflex many use).

http://www.fontspace.com/american-philological-association/new-athena-unicode

Correction once again: New Athena is a nice one, but it's Gentium and GentiumAlt that have the inverted breve circumflex:

http://scripts.sil.org/cms/scripts/page.php?site_id=nrsi&id=gentium