What you need to do is grab the next marker for each substitution. Here's one way of doing it, using /e so you can execute Perl code in the replacement.

$htmlfile =~ s/<a\s+href\s*=\s*(["']?)(http.*?)\1>/
               @markers or die "More URLs than markers.\n";
               qq{<a href="$2} . shift(@markers) . '">'/gie;

@markers and die "More markers than URLs.\n";
[download]

However, this approach still has all the drawbacks of using a regex to match HTML. Using a proper HTML parser would give you a much more robust solution.