The buk function can (very rarely) produce replacements which are shorter than requested (does not zero-pad). Also, buk's function will favor replacements which start with a non-zero digit (isn't uniform).

Good catches both.

I believe that this version corrects both problems without unduly impacting its performance:

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

Examples:

A message 031 of 9150
A message 963 of 0677
A message 477 of 1689
A message 565 of 7675
A message 074 of 6471
A message 235 of 6949
A message 724 of 6703
A message 445 of 6304
A message 991 of 3243
A message 100 of 8825
A message 395 of 2102
A message 406 of 2886
A message 534 of 7045
A message 225 of 8037
A message 443 of 5097
A message 539 of 7089
A message 090 of 7777
A message 208 of 9697
A message 432 of 5864
A message 668 of 7766
A message 913 of 0511
A message 718 of 7972
A message 834 of 8521
A message 064 of 1745
[download]