So, you've got
%$hash whose values are arrayrefs, and you've got
%$values whose keys are things you're looking for, and you want to find those keys
$k in
%$hash such that
@{$hash->{$k}} contains a key from
%$values. Is that the problem you're trying to solve?
Assuming it is, then it seems grep and array are pretty much what you're after (try as you might to avoid them), since you're asking for $k such that grep { $values->{$_} } @{$hash->{$k}} is nonempty.
OK, this isn't going to work that well for large lists, because grep can't short-circuit and you'll waste time after you "already" know the answer is yes. Maybe wait for Perl 6? No, probably not a good idea. So you'll need to do your own short-circuiting by iterating over @{$hash->{$k}} and quitting when you've found something that matches.
Since nothing is sorted anywhere in this exercise, I don't think you'll do much better than "iterate over the keys of %$hash, then iterate over the entries in the arrayref and check each one".
