You can get the effect you're after if you turn your hash into a dispatch table, then deref the sub to get its contents in the substitution side of the regex. This won't trigger undefined warnings for $1. The /e modifier treats the substitution side of the regex as perl code, which is why the sub executes. See perlretut for further information.

#!/usr/bin/perl
use strict;
use warnings;

my %fill = (
    'M(ary)' => sub {"G$1"},
);


while (my $line = (<DATA>)) {
    foreach my $key (keys %fill) {
        if ($line =~ /$key/) {
            $line =~ s/$key/&{$fill{$key}}/e;
        }
    }
    print "$line";
}

__DATA__
Mary has a little lamb

__END__
$ ./reghash.pl 
Gary has a little lamb
[download]

I just realized that Storable won't save a sub, so this solution probably isn't what you want if you need to save the struct to a file.

-stevieb