Put another loop around the loop over the diagnoses:

my @Search = qw( 6280 3141 2718 1414 );
my %frequency;
for my $Search (@Search) {
  for my $diag ( keys %diags ) {
    if( my @found = grep { $_ eq $Search } @{$diags{$diag}} ) {
      my $found = join ",", @found;
      print "Primary diagnosis: $diag, $found\n";
      $frequency{$Search}++;
    }
  }
}
[download]

and then do something based on the %frequency of found diagnoses.