I think building up a subref by evaluating constructed code is likely the best option.

my $subCode = "sub {";
$subCode.=(join "\n",
             map {'$_[0]=~s/'.$_.'/'.$iso8859{$_}.'/g;'}
                   keys %iso8859);
$subCode.="}";

print "$subStr\n";
my $sub=eval $subStr;

$sub->($string);
[download]

You want to make sure that none of the keys appear in any of the substitution values, of course, or this gets more complicated...
--
Mike

Edit: D'oh, took too long writing my response, my first 2 alternatives had already been posted once I hit submit, so edited them out...