I take it you want to sort first by the key which contains the highest score, and then within each key by that key's score. Here's one way to do it:

Update: removed unnecessary intermediate array

my @sorted;
for my $key (keys %entry) {
    my $scores = $entry{$key}{'Score'};
    my $locations = $entry{$key}{'Location'};
    my @array = map { [ $key, $scores->[$_],$locations->[$_] ] } 0 .. 
+$#$scores;
    @array = sort { $b->[1] <=> $a->[1] } @array;
    push(@sorted, [ $array[0][1], \@array ]);
}
@sorted = sort { $b->[0] <=> $a->[0] } @sorted;

for my $array (@sorted) {
    my $aoa = $array->[1];
    for my $result (@$aoa) {
        print "$result->[0] $result->[1] $result->[2]\n";
    }
}
[download]

Output:

TRA 23 4-19
TRA 15 7-15
TRA 2 78-120
BLA 10 2-10
BLA 5 1-10
[download]