I believe the core fonts (i.e. what you get via $pdf->corefont(...) ) simply don't work with Unicode (investigation of the sources and extensive playing around essentially confirmed my suspicion that the generated font descriptions are always classical "Type 1" with an 8-bit encoding vector).  I'd be happy to be proven wrong, though!

OTOH, when you use an appropriate TTF font which has the required glyphs, things work just fine:

#!/usr/bin/perl
use strict;
use warnings;

use PDF::API2;

# Create a blank PDF file
my $pdf = PDF::API2->new();

# Add a blank page
my $page = $pdf->page();

my $font = $pdf->ttfont('DejaVuSans.ttf');

my $ustring = "\x{03a7}\x{03b1}\x{03b9}\x{03c1}\x{03b5}!";

# Add some text to the page
my $text = $page->text();

$text->font($font, 20);
$text->translate(80, 710);
$text->text($ustring);

# Save the PDF
$pdf->saveas('test.pdf');
[download]

DejaVu is a free font with very good Unicode coverage (see the unicover.txt file that comes with the package for details).  And if you feel like designing your own glyphs, you can even download the font's FontForge source files...

P.S.: older versions of PDF::API2 (up to the maintainer change with 2.016) shipped with the DejaVu fonts included, so you may already have them under PDF/API2/fonts/.   Otherwise, if you install them somewhere else, you might want to specify the full path to the respective .ttf file.