Here is a confusing but concise recursive function that does what I think you want.

sub hoa2aoh {
    my ($h, @r) = shift; keys %$h;
    my ($k,$v) = each %$h or return [{}];
    delete $h->{$k}, return hoa2aoh($h) if !@$v;
    my $hd = shift @$v; my $r = hoa2aoh($h);
    (exists $_->{$k} ? push(@r, {%$_, $k=>$hd}) : ($_->{$k} = $hd))
        foreach @$r;
    push @$r, @r; return $r;
}
[download]

It destroys the input, so you might need to make a deep copy of it first.

I would explain how it works, but it’s quite a fun puzzle like this. :-)

Update: Roy Johnson (above) has just posted a nicer implementation of the same idea.