This looks fun. And since it appears that you are proposing to use a rather limited subset of regex possibilities, not too hard.

Here's a working roughed-out beginning toward a generic solution for a certain subset of regex possibilities along the lines you describe.

#!/usr/bin/perl -w
use strict;

sub randchrs {
   my ($type, $length) = @_;
   $length ||= '1';
   my @w = ('A'..'Z', 'a'..'z', '0'..'9', '_');
   my @d = ('0'..'9');
   my @chrs;
   for ($type) {
      /w/ && do {@chrs = @w; last};
      /d/ && do {@chrs = @d; last};
      # other options here
   }
   if ( $length =~ /(\d+),(\d+)/ ) {
      $length = $1 + int(rand($2 - $1 + 1));
   }
   my $answer = '';
   for (1..$length) {
      $answer .= $chrs[int(rand(@chrs))];
   }
   return $answer;
}

while ( my $regex = <DATA> ) {
   chomp $regex;
   $regex =~ s/\(?\\([wd])\)?({([\d,]+)})?/randchrs($1,$3)/eg;
   print "$regex\n";
}

__DATA__
STRING: (\w){3}(\d){5}(\w){3,5}
 PHONE: \d{3}-\d{3}-\d{4}
   SSN: \d{3}-\d{4}-\d{3}
  MORE: several word chars: \w{3,8}
 WA_DL: \w{7}\d{3}\w{2}
 STUFF: \w\d\w\d\w\d
 ANGRY: "\w{5,9}", he said, "\w{5,9}, \w{5,9}, and \w{5,9}."
[download]

That might serve to get you started.

Note in passing: your description of the problem is a bit broader than the solution examples you offer, so you may need to tweek things accordingly. You will certainly need to tweek this example anyway.

Grins, David

------------------------------------------------------------
"Perl is a mess and that's good because the
problem space is also a mess." - Larry Wall