You should create the template from the output of the CGI, not from the code.

perl -MCGI=:standard -e 'print popup_menu({ -name    => "query",
                                            -values  => [1, 2, 3],
                                            -labels  => {qw{ 2 label2 
+1 label1 3 label3 }},
                                            -default => 2 })'
<select name="query" >
<option value="1">label1</option>
<option selected="selected" value="2">label2</option>
<option value="3">label3</option>
</select>
[download]

Update

So, using Template, the following seems to work:

Template call:

    template 'index', { name => 'query',
                        options => { label1 => 'Option 1',
                                     label2 => 'Option 2',
                                     label3 => 'Option 3',
                                   },
                        default => 'label2',
                      };
[download]

The template:

<select name="<% name %>" >
    <%- FOR o IN options %>
    <option value="<% o.key %>"
        <%- IF o.key == default %> selected="selected" <% END -%>
><% o.value %></option>
    <%- END %>
</select>
[download]