The problem is that you are pushing each created <td> onto the @rows array, then using that array to create table rows at the end. What you should do is create the row using just the <td>s for that row and push that onto the @rows array. At the end, you can just use the @rows array as an argument to table(). Your code should look like this:

my @rows;
my @headings = (th(['Foo','Bar']));
push(@rows, Tr(@headings));

my @row1 = (td({-rowspan=>'2'},'foo1'));
push(@row1,td('bar1'));
push(@rows,Tr(@row1));

my @row2 = (td(['bar2']));
push(@rows,Tr(@row2));

my @row3 = (td({-rowspan=>'2'},'foo2'));
push(@row3,td('bar3'));
push(@rows,Tr(@row3));

my @row4 = (td(['bar4']));
push(@rows,Tr(@row4));

print start_html('foobar'),
  table({-border=>'1'},@rows),
end_html;
[download]

The above code produces:

Foo	Bar
foo1	bar1
	bar2
foo2	bar3
	bar4