I don't know about with PDF::Template, but when I use PDFLib, I do this in order to make accented characters like that work:

my $pdf = pdflib_pl::PDF_new();
pdflib_pl::PDF_set_parameter($pdf, "textformat", "utf8");
[download]

of course this means that the text you are inserting must be utf8 and not Latin-1, but Encode can take care of that for you.

Now as for how to make it all work with PDF::Template, I suggest you do a little source diving, the code is readable and the internals are very consistent so it should be pretty obvious where you would need to patch stuff.