Greetings,
Just some updates to your code. I declared %mv in the main scope as "our" so it can be localized in your &domatch() sub later on. The code below works fine for me.

#!/usr/bin/perl -w
use strict;
use re 'eval';

my @strings = ('test_001022','test_585381','test_389742','test_330104'
+);

my $capture = 'test_%a%b';

#added our to your %mv declaration so it can be localized in &domatch(
+);
our %mv;

my %matchers = ('a' => '(\d{2})(?{ $mv{a} = $^N })',
                'b' => '(\d{4})(?{ $mv{b} = $^N })'
               );

sub addmatchers {
        my ($regex) = @_;

        $regex =~ s/%(.)/$matchers{$1}/g;
        return $regex;
}

sub domatch {
        my ($str, $regex) = @_;

        #localize %mv
        local %mv;

        if ($str =~ /$regex/) {
                if (keys %mv == 0) {
                        print "No keys in hash.\n";
                        return 0;
                } else {
                        return \%mv;
                }
        } else {
                return 0;
        }
}

print "original pseudo-regex: $capture\n";
my $r = addmatchers($capture);
print "modified regex: $r\n\n";

foreach my $str (@strings) {
        print "Matching on $str\n";
        my $result = domatch($str,$r);
        if ($result) {
                print "Result:\n";
                foreach my $k (keys %{$result}) {
                        print "\t$k => $result->{$k}\n";
                }
        } else {
                print "No match. ($r)\n";
        }
}
[download]

Here is the output I get

original pseudo-regex: test_%a%b
modified regex: test_(\d{2})(?{ $mv{a} = $^N })(\d{4})(?{ $mv{b} = $^N
+ })

Matching on test_001022
Result:
    a => 00
    b => 1022
Matching on test_585381
Result:
    a => 58
    b => 5381
Matching on test_389742
Result:
    a => 38
    b => 9742
Matching on test_330104
Result:
    a => 33
    b => 0104
[download]

-InjunJoel