You could simply use @values = sort @values, since this checks the first two digits before the rest, yielding your ordering.
And if you are interested, it is also more efficient:

#!perl

use strict;
use warnings;

use Benchmark;

my @array = (
'04=critical',
'02=informational',
'01=unknown',
'10=test',
'03=warning',
'08=foo',
);

sub substr_num {
   @_ = sort { substr($a, 0, 2) <=> substr($b, 0, 2) } @array;
}

sub substr_str {
   @_ = sort { substr($a, 0, 2) cmp substr($b, 0, 2) } @array;
}

sub standard_str {
   @_ = sort { $a cmp $b } @array;
}

sub standard {
   @_ = sort @array;
}

timethese (
  100000,
  {'Numeric with Substring' => '&substr_num',
   'String Cmp with Substring' => '&substr_str',
   'Standard String Cmp' => '&standard_str',
   'Standard' => '&standard'}
);
[download]

Yields the output:

Benchmark: timing 100000 iterations of Numeric with Substring, Standar
+d, Standard String Cmp, String Cmp with Substring...
Numeric with Substring:  2 wallclock secs ( 2.47 usr +  0.00 sys =  2.
+47 CPU) @40502.23/s (n=100000)
Standard:  2 wallclock secs ( 1.59 usr +  0.00 sys =  1.59 CPU) @ 6277
+4.64/s (n=100000)
Standard String Cmp:  2 wallclock secs ( 1.59 usr +  0.00 sys =  1.59 
+CPU) @ 62735.26/s (n=100000)
String Cmp with Substring:  2 wallclock secs ( 2.31 usr +  0.00 sys = 
+ 2.31 CPU) @ 43233.90/s (n=100000)
[download]

And therefore the Ranking

• Standard
• Standard String Cmp
• String Cmp with Substring
• Numeric with Substring

Sometimes it's as simple as it seems :).
Cheers, CombatSquirrel.