I like your package solution, as well as the arguments for it. This package can easily be extended to work for any number of arrays, not only two. The calling code stays the same.

package All_In;

use strict;
use warnings;


sub new {
    my $class = shift;

    my $self = [];

    for my $aref (@_) {
        my %h;
        @h{ @$aref } = ();
        push @$self, \%h;
    }

    bless $self, $class;
}

sub qualify {
    my $self = shift;

    for my $href (@$self) {
        return 0 if ! grep { exists $href->{$_} } @_;
    }
    return 1;
}

1;
[download]