I agree with Pustular Postulant that the code can be slightly simplified and that it is beneficial to clearly define the base case. In essence this problem is simply one of data structure traversal. I think you can take advantage of the fact that each hash entry is an array to simplify the problem to a 2-dimensional array traversal. Here's my code. No better than above, but a slightly different approach. I extracted the data structure to a global to simplify the code in order to highlight the traversal logic.

#!/usr/bin/perl
use strict;

my %set = (
       'foo' => [1, 2, 3],
       'bar' => ["A", "B", "C"],
       'biz' => ["Y", "Z"],
      );
my @keys = sort keys %set;
my $rows = @keys - 1;
my @RESULTSET = ();

sub enumerate {
    my $row = shift;
    my @result = @_;

    my @row_data = @{$set{$keys[$row]}};

    foreach my $data (@row_data) {

    # Base Case
     if ($row == $rows) {
        my $item;
        my @copy = (@result, $data);
        for (my $i; $i < @copy; $i++) {
        $item->{$keys[$i]} = $copy[$i];
        }
         push @RESULTSET,$item;
     }

    # Recursive Case
    enumerate($row+1, (@result, $data)) if ($row < $rows);
    }
}


enumerate(0,());
foreach my $item (@RESULTSET) {
    foreach my $key (@keys) {
    print $key ." => ". $item->{$key} .", ";
    }
    print "\n";
}
[download]