I am not sure this is what you want, but I tried like this.

use strict;
use warnings;
use utf8;
use charnames ();

#create replace table with charname
my ($str, %table);
$str='Vals På Vinkelgränd';

for (129 .. 255 ){ #iso-8859-1 128 to 255
    my $name=charnames::viacode($_);

    next if (! defined ($name));

    #in case "LATIN CAPITAL LETTER A WITH..." => maybe "A" is replace 
+letter?
    if ( $name =~ m/\w+\s+\w+\s+\w+\s(\w+)\s+/ ){
        $table{chr($_)} = $1;
    }
}

#replace
print "$str\n";
$str =~ s/(.)/exists($table{$1}) ? $table{$1}: $1/eg;
print "$str\n";

__DATA__
this prints 
Vals På Vinkelgränd
Vals PA VinkelgrAnd
[download]

Or how about escape it with URI module? regards.

update: I also tried graff's way with Unicode::Normalize. It worked like a charm.