But javascript is not needed.

The following works for me, fully escaping all binary stuff in the value array, just using CGI (and URI::Escape for serialization as proposed by you)

#!perl
use strict;
use CGI;
use URI::Escape;
my $cgi = new CGI;
my $i = 0;
my @Values = map { uri_escape pack('c', $i++) } 1..10;
my %Labels = map {$_, "Label$_"} @Values;
my $size = @Values - 1;
my $attr = 'listbox';

my @rightParams = (
  -class=>'writeField',
  -name=>$attr,
  -values=>\@Values,
  -size=>$size,
  -multiple=>'true',
  -labels=>\%Labels,
);

my @selected = $cgi->param($attr);
my @all = $cgi->param('theValues');

print $cgi->header(),
  $cgi->start_html(-title=>$attr),
  $cgi->start_form(),
  $cgi->scrolling_list(@rightParams),
  $cgi->p('all (from hidden field): ', join(q(, ), @all)),
  $cgi->hidden(-name=>'theValues', -default=>\@Values),
  $cgi->p('you selected: ', join(q(, ), @selected)),
  $cgi->submit(),
  $cgi->end_form(),
  $cgi->end_html(),
  ;
[download]

Deserialize with uri_unescape as needed.