In case you want the keys to include meta-characters that you don't want to treat as such, you might want to "protect" them:

#!/usr/bin/perl -w
use strict;

my %changes=(  foo  => 'toto',
               bar  => 'tata',
              'fo*' => 'to*',
            );
my $changeList = join('|', map { "\Q$_\E"} keys %changes);

my $string= "foo bar fo*";
$string =~ s/($changeList)/$changes{$1}/g;
print $string;
[download]

This way $changeList looks like (\Qkey1\E|\Qkey2|...), which instructs the regexp engine to treat everything between \Q and \E as a literal.