Naive and brutal, but works for me ;-)

use strict;
use warnings;

use Inline 'C';

use constant ZERO_START     => 0;   # digit-sequence allows 0 start
use constant NON_ZERO_START => 1;   # digit-sequence must not start wi
+th a leading 0

msg_subst_seed((time() + $$) % 32000); # just for tests, not a good id
+ea where security matters

do {
  my $x = msg_subst("3x: ({\\d4})x({\\d1})x({\\d10})", NON_ZERO_START)
+;
  print "[$x]\n";
};

print msg_subst("empty: ({\\d0})\n",   ZERO_START);
print msg_subst("$_-dig: ({\\d$_})\n", ZERO_START) for (1..10);

print msg_subst("2x    : ({\\d3}) x ({\\d3})\n", NON_ZERO_START);

print msg_subst("huge:  ({\\d99})\n",  ZERO_START);
print msg_subst("err:   ({\\d100})\n", ZERO_START);
print msg_subst("err:   ({\\d-10})\n", ZERO_START);

print msg_subst('overflow: {\d99}{\d99}{\d99}{\d99}{\d99}{\d99}{\d99}{
+\d99}{\d99}{\d99}{\d99}'."\n",
                 ZERO_START);

__END__


__C__

  #include <stdint.h>

  /* see: http://stackoverflow.com/questions/1167253/implementation-of
+-rand  */

  static uint32_t z1 = 12345, z2 = 12345, z3 = 12345, z4 = 12345; /* s
+eed */

  void msg_subst_seed(int seed) { /* TODO: needs improvement */
     if (seed < 0) seed = -seed;
     if (!seed)    seed = 1;
     z1 = seed;                   /* z1: positive and >= 1 */
  }

  uint32_t lfsr113_Bits (void) {
    uint32_t b;
    b  = ((z1 << 6) ^ z1) >> 13;
    z1 = ((z1 & 4294967294U) << 18) ^ b;
    b  = ((z2 << 2) ^ z2) >> 27;
    z2 = ((z2 & 4294967288U) << 2) ^ b;
    b  = ((z3 << 13) ^ z3) >> 21;
    z3 = ((z3 & 4294967280U) << 7) ^ b;
    b  = ((z4 << 3) ^ z4) >> 12;
    z4 = ((z4 & 4294967168U) << 13) ^ b;
    return (z1 ^ z2 ^ z3 ^ z4);
  } /* see.. until here */

  

  char get_digit()  {/* iterator to get an ASCII digit in range '0'..'
+9', the naive way... */
    static int       count = 0;
    static uint32_t  drawn_rand;
    char             digit;

    if (!count) {
       drawn_rand = lfsr113_Bits();
       count = 8;
    }
    digit = (char) ('0' + drawn_rand % 10);
    drawn_rand /= 10;
    count--;

    return digit;
  }


  SV * msg_subst(char* msg, int mode) {
    static char  buf[1024];
           /* keep the result smaller than this, increase the static b
+uffer, or use malloc() */
    char  *to   = buf;
    char  *from = msg;

    while(*from  &&  (to-buf) <= 1000) {
      /* for simplicity, we allow {\d0} .. {\d99} only */
      if (*from == '{'  && from[1] == '\\' && from[2] == 'd' && isdigi
+t( from[3] )) {
        int i;
        int count    = from[3] - '0';
        int consumed = 4;

        if ( isdigit(from[4]) ) {
          count = count * 10 + from[4] - '0';
          consumed++;
        }

        if ( from[consumed] == '}' ) { /* found a valid {\d##} sequenc
+e */
          if (count && mode == 1) {
            count--;
            *to = get_digit();
            while (*to == '0') { *to = get_digit(); } /* no leading ze
+ros wanted */
            to++;
          }
          for (i=0; i<count  &&  (to-buf) <= 1000 ; i++) *to++ = get_d
+igit();
          from += consumed;
        } else { /* err, just copy what we saw */
                 for (i=0; i<consumed; i++) *to++ = from[i];
                 from += consumed -1;
       }

      } else { /* no {\d++} sequence in sight */
        *to++ = *from;
      }

      from++;
    }

    *to = '\0';
    if ( (to-buf) >= 1000 ) strcpy( to, "... *OVERFLOW*!\n");

    return newSVpv(buf, strlen(buf));
  }



/* further improvements:
  - profile / this alternative "can" be faster
  - other/better random generator or lookup-table ()
  - parse pattern once (if pattern stays constant for a sufficiently l
+ong period of time)
  - more than 99 digits
  - Modes: HEX, ASCII, SET(...), RANGE(...)
  - tweak "use inline C;"
  - pre-compute messages if possible
  - return a list of results
  - find more buffer overflows ;-)
  - find mem-leaks?
  - set $!
  - ...
*/
[download]

Sample:

[3x: (5800)x(9)x(4119272153)]
empty: ()
1-dig: (6)
2-dig: (00)
3-dig: (286)
4-dig: (3538)
5-dig: (76912)
6-dig: (152922)
7-dig: (1998601)
8-dig: (46526790)
9-dig: (272269142)
10-dig: (5036180257)
2x    : (270) x (295)
huge:  (60698211971351646325662438145076882977674264083631891784014981
+6984333515486911733872823592611980610)
err:   ({\d100})
err:   ({\d-10})
overflow: 388337913014518572079085655682352923685268720200399379872225
+309937696652401652578874749078259328418468960924412471336333591725866
+610726754040840249257924549575536281471052995818025767742622376415863
+863933450041956239915916349295988704367621957622747170445376882427886
+836368075301197163788171910212466615189214921253457526440240130287642
+877297593187189458587800219270169705119636312020472283690712168123351
+112899925547204701597189413213272345551314154916747140042506436194250
+360536730048179486951946798572111575588675513637404504421938424450645
+872242712239584218866179138498996988181042546504722655259441150264820
+656960415909356582097541742743117114058581773895455908059546695344897
+361883153435808150852670180088922568961467160025338460179243921987976
+441004315513268035989754880873846622730659638610226282538414297658365
+180965342365181518413709147137791131035270552146178096818064703332869
+696209005692384041910395288531887465999649751307270627069753831067510
+2369072243267355810846576590914699... *OVERFLOW*!
[download]