This is the way I would tend to approach this type of problem. See haukex's article Building Regex Alternations Dynamically (a technique I seem to have posted about quite often recently).

c:\@Work\Perl\monks>perl -wMstrict -le
"my $text = 'text with a <%VAR%> and <%FOO%> to interpolate <%OOPS%>';
 print qq{'$text'};
 ;;
 my $vars = {
   'VAR' => 'Value Taken From A Data Structure',
   'FOO' => 'Another One',
   };
 ;;
 my $rx_pre  = qr{ <% }xms;
 my $rx_post = qr{ %> }xms;
 ;;
 my ($rx_var) =
   map  qr{ $_ }xms,
   join '|',
   map  quotemeta,
   reverse sort
   keys %$vars
   ;
 print 'regex: ', $rx_var;
 ;;
 $text =~ s{ $rx_pre ($rx_var) $rx_post }{$vars->{$1}}xmsg;
 print qq{'$text'};
 ;;
 log_unknown(\$text, $1, $-[1]) while $text =~ m{ ($rx_pre .*? $rx_pos
+t) }xmsg;
 ;;
 ;;
 sub log_unknown {
   my ($sr_text, $unknown_tag, $offset) = @_;
   ;;
   print qq{unable to interpolate '$unknown_tag' at offset $offset}
   }
"
'text with a <%VAR%> and <%FOO%> to interpolate <%OOPS%>'
regex: (?msx-i: VAR|FOO )
'text with a Value Taken From A Data Structure and Another One to inte
+rpolate <%OOPS%>'
unable to interpolate '<%OOPS%>' at offset 77
[download]

One might also define a regex to match the acceptable pattern of any key (interpolation tag) in the  $vars hash, then use it both to check those keys when building the  $rx_var regex and then later in place of  .*? to look for unknown/failed interpolations.