You could handle this with an eval, although depending on where your input is coming from, that could be dangerous. (note, the / inside your regex will cause problems in your example)

$regex = eval $regex;
[download]

As a better alternative, you could use something like sprintf.

my $s = 'Tue Feb  8 11:11:11 2005: blah blah blah';

my $regex = "^%s %s\s+%s \d{2}:\d{2}:\d{2} %s:';

my $wday = 'Tue';
my $mon = 'Feb';
my $mday = '8';
my $year = '2005';

findString($s, $wday, $mon, $mday, $year);

sub findString {
  my $line = shift;
  my $pattern = sprintf($regex, @_);
  print "found\n" if $line =~ /$pattern/;
}
[download]