Why not just do the simple way:

my %hash = (
    red    => 2,
    pink   => 1,
    orange => 4,
    black  => 3,
    blue   => 4
);

my ($max, @maxKeys);
for (keys %hash) {
  $max = $hash{$_} unless $max;
  if ($hash{$_} > $max) {
      @maxKeys = ($_);
      $max = $hash{$_};
  } elsif ($hash{$_} == $max) {
      push @maxKeys, $_;
  }
}

print "$_: $hash{$_}\n" for @maxKeys;
[download]

This will only touch each value once, which is necessary anyway for this type of problem, giving you a O(N) solution.

Update: My bad, didn't see the part about printing the keys and values, so I have updated my code accordingly.