Following moritz's suggestion, I used Text::Unidecode and utf8:

#!/usr/bin/perl -l

use strict;
use warnings;
use utf8;
use Text::Unidecode;

binmode STDOUT, ":encoding(utf8)";
my $guess1 = unidecode("Vals P\403 Vinkelgr\403nd");
my $guess2 = print unidecode($guess1);
[download]

Note: It works on my terminal, but not on perlmonks.org. Sorry.