This looks to be about 10% faster on my dataset:

foreach my $constant (keys %constants) {
    $string = join $constants{$constant}, split /$constant/, $string;
}
[download]

It's a lot less clear, though. Maybe if you build the regexes beforehand, you'll see a speed benefit? Look at the qr/// operator.