Even doing the extra work that wasn't asked for (sorting by "foo" the records where "bar" is equal), it isn't particularly hard. I'll sort "bar" descending and then "foo" ascending to illustrate the techniques a bit better:

my @list= <DATA>;
@list= @list[
    map { unpack "N", substr($_,-4) }
    sort
    map {

        # Only these two lines had to be written:
        my( $foo, $bar )= $list[$_] =~ / (\d+) /g;
        ~pack("N",$bar) . pack("N",$foo)

          . pack "N", $_
    } 0..$#list
];
print @list;
__END__
Item1 - 2 foo, 2 bar
Item2 - 0 foo, 1 bar
Item3 - 1 foo, 3 bar
Item4 - 1 foo, 2 bar
Item4 - 3 foo, 2 bar
Item4 - 0 foo, 2 bar
[download]

Yes, this screams to be put into a module... (:

Rather than ~pack"N", you can also use ~sprintf"%09d" or even ~(length($n).$n)."\0" if you are dealing with non-negative integers, but pack"N" is nice in that it handles negative integers and rather large numbers and is fast.