The regex only works if the hash contains cat and dog in the same value, but judging from the description, that's not what you want.

Instead of trying to be too clever, I'd use something like this:

use 5.014;
use warnings;

my @hashes = (
    { bla => 'cat', blubb => 'dog' },
    { only => 'cat' },
    { just => 'dog' },
);

sub hr_contains_cat_and_dog {
    my $hr = shift;
    my ($has_cat, $has_dog);
    for (values %$hr) {
        $has_cat = 1 if /cat/i;
        $has_dog = 1 if /dog/i;
    }
    return $has_cat && $has_dog;
}

my @result = grep hr_contains_cat_and_dog($_), @hashes;

use Data::Dumper;
print Dumper \@result;
__END__
$VAR1 = [
          {
            'bla' => 'cat',
            'blubb' => 'dog'
          }
        ];
[download]