Try something like the following:

use strict;

my %Column = ('TableName' => 'MyTable', 'Date' => '12-3-1979');
my $Template = join('', <DATA>);
$Template =~ s/%%(.*?)%%/$Column{$1}/g;

print $Template;

__DATA__
** FastLoad Script for %%TableName%%
** -------------------------------------------------------------------
+------------------------------------------------
** Generated by LoadGen
** -------------------------------------------------------------------
+------------------------------------------------
** What | Who | When       | Why
** -------------------------------------------------------------------
+------------------------------------------------
** 1.00 | %%Author_Initials%% | %%Date%% | Original Version
** -------------------------------------------------------------------
[download]

Your problem was that your regex was greedy, taking the maximum length match rather than the shortest match. You can fix this by doing .*? instead of .* As you can see from the small section of test code above, the substitutions should work fine for you now.