Thanks Anonymous Monk and AnomalousMonk,

So, the technique is to doubly double-stringify the RHS before doubly evaluating it! Analogous to the trick of using @{ [...] } to interpolate a function-returned list into a string.

I like String::Interpolate (the module, not its documentation!):

#! perl
use strict;
use warnings;
use String::Interpolate qw( interpolate );

my $c = q{asdfghjk};

my @regex =
(
    { lh => q{(gh)}, rh => q{__$1__}, }, 
    { lh => q{(h_)}, rh => q{_h!$1!}, }, 
);

print q{Original: }, $c, "\n";

for my $i (0 .. $#regex)
{
    $c =~ s/ $regex[$i]{lh} / interpolate($regex[$i]{rh}) /ex;
}

print q{Final: }, $c, "\n";
[download]

Output:

13:37 >perl 1352_SoPW.pl
Original: asdfghjk
Final: asdf__g_h!h_!_jk

13:37 >
[download]

Cheers,