Try this (updated to reflect the error toolic caught below)(Further updated to correct flaws reported by dualafn):

sub substitute{ 
    my $s = shift; 
    $s =~ s[\{\\d(\d+)\}][ substr int( 1e10 + rand 1e10 ), 1, $1 ]ge; 
    return $s 
};;

print substitute( $_ ) for 'A message {d3} of {d4}';;
A message 425 of 3404

print substitute( $_ ) for 'A message {d3} of {d4}';;
A message 860 of 3797

print substitute( $_ ) for 'A message {d3} of {d4}';;
A message 453 of 2262

print substitute( $_ ) for 'A message {d3} of {d4}';;
A message 761 of 5898

print substitute( $_ ) for 'A message {d3} of {d4}';;
A message 321 of 4182

print substitute( $_ ) for 'A message {d3} of {d4}';;
A message 924 of 5054
[download]

[14:37:57.99] C:\test>junk
               Rate    nar_func    mca_func toolic_func    buk_func
nar_func     2449/s          --        -26%        -66%        -78%
mca_func     3287/s         34%          --        -55%        -70%
toolic_func  7231/s        195%        120%          --        -35%
buk_func    11125/s        354%        238%         54%          --
[download]