Because the order matters. If the regex checked for 'yy' before 'yyyy', then 'yyyy-mm-dd' would translate to '%y%y-%m-%d'.

use warnings;

sub translate_date_format
{
    my %tr = (
        yyyy  => "%Y",
        yy    => "%y",
        mmmm  => "%B",
        mmm   => "%b",
        mm    => "%m",
        m     => "%e",
        ww    => "%V", # or %U
        w     => "%w", # or %u
        j     => "%j",
        dddd  => "%A",
        ddd   => "%a",
        dd    => "%d",
        d     => "%e",
        HH    => "%H",
        H     => "%k",
        hh    => "%I",
        h     => "%i",
        MM    => "%M",
        A     => "%p",
        AM    => "%p",
        PM    => "%p",
        a     => "%P",
        am    => "%P",
        pm    => "%P",
        SS    => "%S",
        ZZZ   => "%Z",
        );

    my $str = shift;
    $str =~ s/(?<!%)$_/$tr{$_}/g for reverse sort keys %tr;
    return ($str);
    }

### Test #############################################################
+#########

use POSIX;
use Time::Piece;

my @test = (
    "yyyy-mm-dd",  "d/mm/yy",
    "H:MM:SSAM",   "HH:MM:SSpm",
    "mmm ddd, yy", "dddd, mmmm dd, yyyy HH:MM:SS",
    );

foreach (@test) {
    my $tdf = translate_date_format ($_);
    print "$_ => '$tdf'\n";

    my $date = POSIX::strftime ($tdf, localtime ());
    print "  POSIX: $date\n";

    my $t = localtime ();
    $date = $t->strftime ($tdf);
    print "  Time::Piece: $date";
    $date = $t->strptime ($date, $tdf);
    print " => $date\n";
    }
[download]

I also see (using warnings) yet another reason never to use AM/PM :) :

HH:MM:SSpm => '%H:%M:%S%P'
  POSIX: 11:39:52am
garbage at end of string in strptime: am at /pro/lib/perl5/site_perl/5
+.20.0/x86_64-linux-thread-multi-ld/Time/Piece.pm line 469.
  Time::Piece: 11:39:52am => Thu Jan  1 11:39:52 1970
[download]

reverse sort keys %tr

I'd probably sort them by negative length and join them to a single regex:

my $regex = '('
          . join('|', sort { length $b <=> length $a } keys %tr)
          . ')';
$str =~ s=$regex=$tr{$1} // $1=ge;
[download]

لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ