Если у вас есть одномерный массив, вы можете использовать array_map ();
** Edit: у меня был некоторый код здесь, но после тестирования он не работает.
Что касается вашего редактирования.
То, что Foo находится в конце строки, не означает, что str_replace больше не будет работать.
echo str_replace("foo","foo-bar","mycrazystringwithfoorightinthemiddleofit");
все равно вернется
mycrazystringwithfoo-barrightinthemiddleofit
Если ваш массив представляет собой древовидную структуру произвольной глубины, то неизбежно, что вам придется использовать рекурсию, и проблема становится нетривиальной. Вы можете проверить
Функция array_recursive_walk ().
здесь
Надеюсь, это поможет.