I'm amused that you do the mapping in the sort block, instead of properly computing the value once. Perhaps you meant:

use strict;

my %map = (
   S => 0, M => 1, L => 2, Xl => 3
);

my @sorted = 
   map { $_->[0] }
   sort {
      $a->[1] <=> $b->[1] or
      $a->[2] cmp $b->[2]
   }
   map { /^(\w+:\s+(\w+),\s+\w+:\s+(\w+))$/ ? [$1, $map{$2}, $3] : () 
+} <DATA>;

print join("\n", @sorted);

__DATA__
size: L, color: White
size: M, color: Orange
size: M, color: White
size: M, color: White
size: S, color: Orange
size: S, color: White
size: Xl, color: Orange
size: Xl, color: White
size: Xl, color: White
[download]