Logically, your strings will have between 4 and 6 characters. By left padding every string with asterisks to a standard length of 6 characters, you no longer need to perform a natural sort to accommodate missing zeros or asterisks.
Using array_multisort() will offer better performance because the data-mutating step will make n iterated calls of sprintf(), but usort() will call preg_replace() twice and strnatcmp() once n log n times (IOW, it's more expensive).
'*6 means left pad the string (%s) with the * character to ensure that the string has a length of 6 characters.
Code: (Demo)
$array = [
'12:00',
'*15:00',
'9:00',
'22:00'
];
array_multisort(
array_map(fn($v) => sprintf("%'*6s", $v), $array),
$array
);
var_export($array);
Output:
array (
0 => '9:00',
1 => '12:00',
2 => '*15:00',
3 => '22:00',
)
Of course this will work just the same too if you don't want to make mapped calls of anything: (Demo)
array_multisort(
str_replace('*', '', $array),
SORT_NATURAL,
$array
);
var_export($array);