I agree with chromatic except I see a small problem with his solution. With the regular expression:

$str =~ s/(^|[^\%](?:\%\%)*)\%\{?([_a-zA-Z]\w*)\}?/"$1".$env->{$2}/ge
[download]

it would match on something like %{FOO or %FOO}.

How to aviod that in a single RE? I'm not quite sure... Time for me to do some digging....