As a starting point:

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;
}
[download]

You didn't present a runable example, so I can't do a benchmark. So, I just hope to have a faster version.

McA