I'm sure there are many nasty traps here, but you could take a look at Text::Diff.

use strict;
use warnings;
use Algorithm::Diff qw(diff);

my @strs = (
    ['ABCÅD', 'ABCD'],
    ['ABCÄD', 'ABCëëD'],
    ['ABCááD', 'ABCèD'],
    );
my %xlate;

for (@strs) {
    my ($org, $mod) = @$_;
    my @orgSeq = split //, $org;
    my @modSeq = split //, $mod;
    my (@diffs) = diff (\@orgSeq, \@modSeq);

    for my $diff (@diffs) {
        my @sub = grep {$_->[0] eq '-'} @$diff;
        my @add = grep {$_->[0] eq '+'} @$diff;

        next if ! @sub; # Bogus added characters
       
        $xlate{join '', map {$_->[2]} @sub} = (join '', map {$_->[2]} 
+@add) || '';
    }
}

print "'$_' => '$xlate{$_}'\n" for sort keys %xlate;
[download]

Prints:

'Ä' => 'ëë'
'Å' => ''
'áá' => 'è'
[download]

Update: changed bogus use Text::Diff to use Algorithm::Diff and clean up code to suit.