Вот мои результаты небольшого полевого теста:
preg_replace("/\(|\)/", "", $str): 1.590735912323
preg_replace('/[\(\)]/', '', $str): 1.3762638568878
strtr($str, array('(' => '', ')' => '')): 0.84079194068909
str_replace("(", "", str_replace(")", "", $str)): 0.80222821235657
Последние два почти идентичны, как указал Дж. Бруни.