Here is a quick (=unchecked) one. It could be optimized a bit more but this probably gives the idea. I don't know if there's a better Perl way than using substr.

$l = $#str1>$#str2 ? $#str2 : $#str1;
$val = $l-$#str1 + $l-$#str2;
for $i ( 1..$l ) {
    $val += substr($str1, $i, 1) ne substr($str2, $i, 1);
    last if ($val > $max_diff);
}
return ($val > $max_diff);
[download]