It's basically what I'd do too. I'd just construct the regex myself I guess.
Something along the lines of:
my $match = '('.join( '|', sort keys %replace ).')'; and then use the value in $replace{$1}

It appears from the problem description that the keys are all three characters, but just as a heads-up, you might want to add a reverse to that:

my $match = '('.join('|', reverse sort keys %replace).')';

The reverse ensures that the longest match is found even if some pattern is a prefix of another (which, in my experience, is generally the desired outcome). e.g.:

#!/usr/bin/perl -l
use strict;
use warnings;
my %replace = qw/pre 1 prefix 2/;
my $norev = '('.join('|', sort keys %replace).')';
my $withrev = '('.join('|', reverse sort keys %replace).')';
while (<DATA>) {
    chomp;
    print "Line: $_";
    print "norev <$1>" if /$norev/;
    print "w/rev <$1>" if /$withrev/;
}
__END__
This line contains prefix (which also matches 'pre')
[download]

Should print:

Line: This line contains prefix (which also matches 'pre')
norev <pre>
w/rev <prefix>
[download]