Another way entirely:

~linux> perl -MMath::Cartesian::Product -e 'my %hash = (q|foo|=>[qw|fo
+ol food foot|],q|bar|=>[qw|barricade|]); for (keys %hash) {cartesian 
+{print qq|@_\n|} [$_],$hash{$_}};'
[download]

Produces

bar barricade
foo fool
foo food
foo foot
[download]

TIMTOWTDI