If you really need to use composite keys, then if you order the elements the other way around, you can let perl pick off the fanout number from the front of the string, and just silence the 'not numeric" warnings:

$h{ int( rand 50 ) . ' '. rndStr( 1+int(rand(20) ), 'A'..'Z' ) } =
    'just a placeholder' for 1 ..50;;

print "$_ : $h{ $_ }" for sort{ 
    local $^W; 
    $a <=> $b 
} keys %h;;

0 YLJG : just a placeholder
1 ERHC : just a placeholder
2 UEGHWMGJVWDAUEOJR : just a placeholder
3 TPFZPXPS : just a placeholder
3 VDII : just a placeholder
4 SHHSRQLJVXTOPBYXT : just a placeholder
4 RXWZUUDA : just a placeholder
7 IPSCGIHLBWPR : just a placeholder
9 JRPAZKPXSC : just a placeholder
10 BGE : just a placeholder
11 OI : just a placeholder
11 HYXKTCLHDWCO : just a placeholder
14 QU : just a placeholder
16 ASJOWMLOWWMJWHDRAZ : just a placeholder
17 SQUJMOIM : just a placeholder
18 PFZDZODFMLBCVLTXQF : just a placeholder
18 AYYUCHEUXMNTTVLTJB : just a placeholder
19 KBDNXHCLUHEXSM : just a placeholder
20 EGWOTWSNEBXDISO : just a placeholder
20 QCCXXYEUFMRTYSYDGIBQ : just a placeholder
22 MBGBHAGRDEQXS : just a placeholder
24 IQWSMASGOOKQZC : just a placeholder
27 XRWPIZFKHGNEMTZGEGGB : just a placeholder
27 BHYAWIULV : just a placeholder
28 NNFUODXBGHKGAXKEZJIO : just a placeholder
29 SRQKDZIJVIDDWKQMUEZ : just a placeholder
30 OGFVEODJJGJRTRJ : just a placeholder
32 YMBMILY : just a placeholder
32 GCSQRJHHLJZEX : just a placeholder
33 HNNPVDVXMVPEQTISJ : just a placeholder
34 LCJKOFVJM : just a placeholder
34 HWMLT : just a placeholder
34 CVRFVEYISPLZJN : just a placeholder
36 HUJIAGMCRSSEACCBSES : just a placeholder
37 TLYYNSLVRAMZTXKDMAQC : just a placeholder
38 DAYGYGLMVZMXQTHIJBEV : just a placeholder
40 Q : just a placeholder
40 BNZBSPTUUTQBQMLAD : just a placeholder
41 FDFBWHPUQQRMVV : just a placeholder
42 JKTKYC : just a placeholder
42 LRLOBPONBCPKG : just a placeholder
45 DDBSCVQVKAUP : just a placeholder
45 RNHMIRVLMMYVYRMA : just a placeholder
45 HVETVTKMTUH : just a placeholder
46 EJEQMCIXCMGX : just a placeholder
46 UMIH : just a placeholder
46 GWZM : just a placeholder
46 POOWQOUASNALUX : just a placeholder
49 CZPDKKGAKQZK : just a placeholder
49 UJSMQRNEBQ : just a placeholder
[download]

For your early exit, do the same thing:

for my $key (  sort{ local $^W; $a <=> $b } keys %h ) {

    last if do{ local $^W; 0 + $key } >= 20;
    print "$key : $h{ $key }";
};;

0 YLJG : just a placeholder
1 ERHC : just a placeholder
2 UEGHWMGJVWDAUEOJR : just a placeholder
3 TPFZPXPS : just a placeholder
3 VDII : just a placeholder
4 SHHSRQLJVXTOPBYXT : just a placeholder
4 RXWZUUDA : just a placeholder
7 IPSCGIHLBWPR : just a placeholder
9 JRPAZKPXSC : just a placeholder
10 BGE : just a placeholder
11 OI : just a placeholder
11 HYXKTCLHDWCO : just a placeholder
14 QU : just a placeholder
16 ASJOWMLOWWMJWHDRAZ : just a placeholder
17 SQUJMOIM : just a placeholder
18 PFZDZODFMLBCVLTXQF : just a placeholder
18 AYYUCHEUXMNTTVLTJB : just a placeholder
19 KBDNXHCLUHEXSM : just a placeholder
[download]