Well, you could reduce the input sort list, but at the cost of more comparisons. In this case, only sorting keys that contain the desired $string. Something like:

foreach my $key (sort grep(/$string/,keys %hash)) {
    if($key =~ /^$string(.*)$/) {
       blah;
    }
    if($key =~ /^(.*)$string$/) {
       blah;
    }
}
[download]

This seems to speed things up for large hashes provided the matching list is a pretty small subset of the input.

Update: Since you are return()ing the first time you find a match, the sort() is doing more work than you need. You really need a min() function. There's a node that discussed various ways to implement a min().