My preference is for code to read exactly like the English that describes it. Your spec says "not ... any", so the closest I can come to that is:

use List::MoreUtils qw(any);

foreach my $k (keys %test_hash)
{
  if (not any { exists $_->{$k} } \%hash1, \%hash2, \%hash3, \%hash4)
  {
    print $k;
  }
}
[download]

Of course, "not any" is grammatically the same as "none", i.e., saying "not present in any" is exactly the same, both in meaning and intent, as "present in none", so you could swap it out:

use List::MoreUtils qw(none);

foreach my $k (keys %test_hash)
{
  if (none { exists $_->{$k} } \%hash1, \%hash2, \%hash3, \%hash4)
  {
    print $k;
  }
}
[download]

They should take exactly the same amount of time because they should short circuit exactly the same.

I don't actually suggest this over Anonymous Monk's solution for speed reasons. I suggest this because the code reads linguistically the same as your spec. It just happens that it performs as well or better than the grep solution.

The grep solution actually returns a list in boolean context. My solution returns boolean in boolean context. In my mind, that is a win right there because the code says the same thing as the spec. There are fewer mental logic changes where someone may have to stop and think about how it works. Reading just like the spec means that the maintenance programmer will just be able to read the code without even necessarily being familiar with List::MoreUtils. In fact, the only reason they would check the docs for List::MoreUtils would be to see what other cool things it had.