The rule of thumb seems to fit here: The less code the faster is it:

#!/usr/bin/perl
use strict;
use warnings;
use 5.010;
use Benchmark qw(cmpthese);

my @messages = <DATA>;

cmpthese(1000000, {
    'mca_func' => sub {
        my $out = mca_substitute($_) foreach (@messages);
    },
    'toolic_func' => sub {
        my $out = toolic_substitute($_) foreach (@messages);
    },
});


sub toolic_substitute {
    my $message = shift;
    $message =~ s/\{\\d(\d+)\}/sprintf "%0${1}d", int(rand(10**$1))/ge
+;
    return $message;
}

sub mca_substitute {
    my $message = shift;
    $message =~ s/\{\\d(\d+)\}/myreplace($1)/ge;
    return $message;
}

sub myreplace {
    return '' unless $_[0];

    my $string = '';
    $string .= int(rand 10) for (1..$_[0]);
    return $string;
}




__DATA__
This is a message! {\d3} --- {\d2}
Another {\d3} Message with {\d5}
A {\d1} little {\d6} longer string {\d3}
[download]

On my machine:

               Rate    mca_func toolic_func
mca_func    42955/s          --        -35%
toolic_func 66534/s         55%          --
[download]

McA