Well, this won't necessarily make it faster, but it'll be a lot easier to read. Create a reference to $hash{$key} and use that instead: (note, untested)

my ($key, $msg, $ref);   # stick with the naming convention ;-)
foreach $key (keys %hash) {
    $ref = \$hash{$key};
    foreach $msg (@Messages) {
        if ($ref->{error_message} =~ /$msg/ and
            $ref->{date} =~ $DATE) {
           #
           # Notice one print call will suffice,
           # just line up what you want to print,
           # or concatenate into a single string.
           #
           print RPT "$ref->{packet_id}\t$ref->{origin}\n",
                     "$ref->{date}\t$ref->{qualifier}\n",
# etc.
[download]

Another thing: you don't show what's in @Messages or $DATE. If either of those are constant strings, don't bother with a pattern match at all; use string comparison.

HTH