while($$file =~ 
  m{( <% \s* link_name \s* (\S*) \s* %> )}xg
){
  push @link_names,[pos($$file)-length($1),length($1),$2]
}
#now fetch stuff from database at once
if(@link_names){
     my $sql =
      'SELECT template_id from template_table where '.
      join(' OR ',(('template_name = ?')x @link_names));
     #... you're hopefully using DBI
     $sth->execute( @link_names );
     #...

     #replacement can be done easily and _fast_ because
     # you know the positions of your links and their 
     # length, so use substr(!) here
}