The only way I can see right now to deal with * vis-a-vis glob is to replace it with a character that occurs nowhere else in your data. So maybe (if tybalt89 hasn't already solved this):

c:\@Work\Perl\monks\tel2>perl -wMstrict -MData::Dump -le
"use constant NEVER_PRESENT => qq{\x01};
 ;;
 my $s = 'Prefix5,Prefix6:A,B:*:1,23 value7=10|value88=123';
 ;;
 $s =~ s{ [*] }{${ \NEVER_PRESENT }}xmsg;
 ;;
 my ($keyule, $valule) = split ' ', $s, 2;
 ;;
 $keyule  =~ s{ : }[}:{]xmsg;
 $keyule  = qq[{$keyule}];  print qq{'$keyule'};
 $valule  =~ s{ [|] }{,}xmsg;
 $valule  = qq[{$valule}];   print qq{'$valule'};
 ;;
 my %hash;
 for my $v (glob $valule) {
   my ($vk, $vv) = split '=', $v;
   for my $k (glob $keyule) {
     $k =~ s{ ${ \NEVER_PRESENT } }{*}xmsg;
     $hash{$k}{$vk} = $vv;
     }
   }
 dd \%hash;
"
'{Prefix5,Prefix6}:{A,B}:{☺}:{1,23}'
'{value7=10,value88=123}'
{
  "Prefix5:A:*:1"  => { value7 => 10, value88 => 123 },
  "Prefix5:A:*:23" => { value7 => 10, value88 => 123 },
  "Prefix5:B:*:1"  => { value7 => 10, value88 => 123 },
  "Prefix5:B:*:23" => { value7 => 10, value88 => 123 },
  "Prefix6:A:*:1"  => { value7 => 10, value88 => 123 },
  "Prefix6:A:*:23" => { value7 => 10, value88 => 123 },
  "Prefix6:B:*:1"  => { value7 => 10, value88 => 123 },
  "Prefix6:B:*:23" => { value7 => 10, value88 => 123 },
}
[download]

Ok, now what's the next phase in the dance-of-the-seven-veils requirement disclosure?

Update: BTW: I'm still not convinced that glob is the way to go with this application. An algorithmic permuter (update: such as haukex describes) or parser would be more to my liking, but it's your project.