I can get rid of the errors by using binmode STDOUT, ":encoding(utf8)" but the output is still messed up.

The binmode call is the right thing to do.

Maybe your console doesn't properly work with UTF-8 output? Try to execute this: $ perl -Mcharnames=:full -CS -wle 'print "\N{EURO SIGN}"'

If this shows a Euro sign, everything is fine with your console, and it's indeed a problem in your script. If not, you know what needs fixing.