PHPで以下のような配列があります。

uasort関数を使ってみました。

http://jp2.php.net/manual/ja/function.uasort.php

ただし、スクリプトの文字コードは UTF-8 限定です。

<?php
mb_internal_encoding('UTF-8');
mb_regex_encoding('UTF-8');

//質問通りの並べ替えを実現する
function ore_sort($a, $b) {
    $pat = '/(★)?([^★]*)/ui';
    preg_match($pat, $a, $ra);
    preg_match($pat, $b, $rb);
    if ($ra[1] == $rb[1])   $res = strcmp($ra[2], $rb[2]);
    else                    $res = strcmp($b, $a);
    return $res;
}

$arr = array(
'TEST1-AAA' => '★A1',
'TEST1-BBB' => '★A2',
'TEST1-CCC' => 'A3',
'TEST2-AAA' => '★A4',
'TEST2-BBB' => 'A5',
);

var_dump($arr);
uasort($arr, "ore_sort");
var_dump($arr);
?>

別のやり方で。

<?php
$arr = array(
  'TEST1-AAA' => '★A1',
  'TEST1-BBB' => '★A2',
  'TEST1-CCC' => 'A3',
  'TEST2-AAA' => '★A4',
  'TEST2-BBB' => 'A5',
  );

$result = array_filter($arr, create_function('$a', 'return strpos($a, "A") > 0;'))
+ array_filter($arr, create_function('$a', 'return strpos($a, "A") == 0;')) ;

print_r($result) ;
?>