How about this:

$str =~ s/(^|[^\%](?:\%\%)*)\%
          (\{)?                  # Match and capture 1 or 0 braces
          ([_a-zA-Z]\w*)
          (?(2)\})               # If there's anything in $2, match en
+ding brace
          /"$1".$env->{$3}/gex;  # $3 now instead of $2 here
[download]

This takes advantage of perl's conditional matching operator. From perlre:

(?(condition)yes-pattern|no-pattern)
(?(condition)yes-pattern)

Conditional expression. (condition) should be either
an integer in parentheses (which is valid if the
corresponding pair of parentheses matched), or
lookahead/lookbehind/evaluate zero-width assertion.
 
       Say, 

           m{ ( \( )? 
              [^()]+
              (?(1) \) )
            }x

matches a chunk of non-parentheses, possibly included
in parentheses themselves.
[download]