not so elegant solution :(
<?php
$area = array(
    array(
        'state'   => "TX",
        'city'    => "Austin",
        'newName' => "SoCo (S. Congress Ave.)",
        'oldName' => "South Congress"
    ),
    array(
        'state'   => "NY",
        'city'    => "Buffalo",
        'newName' => "Elmwood Village",
        'oldName' => "Elmwood "
    ),
);
$state = "TX";
$city  = "Austin";
$str1  = "78704 (South Austin), SoCo (S. Congress Ave.), Bouldin Creek";
$str2  = "South Congress";
list($search, $replace) = array_reduce($area,function($carry,$area_item) {
    $carry[0][]=trim($area_item['oldName']);
    $carry[1][]=trim($area_item['newName']);
    return $carry;
}, array());
$result = str_replace($search, $replace, implode(', ',[$str1,$str2]));
$arr1 = explode(", ", $result);
$arr3 = array_diff(array_unique($arr1), array('NA'));
$str3 = trim(implode(", ", $arr3), ", ");
var_dump($str3);
var_dump() result:
string(60) "78704 (South Austin), SoCo (S. Congress Ave.), Bouldin Creek"
updated and commented code below
<?php
// source data array
$area = array(
    array(
        'state'   => "TX",
        'city'    => "Austin",
        'newName' => "SoCo (S. Congress Ave.)",
        'oldName' => "South Congress"
    ),
    array(
        'state'   => "NY",
        'city'    => "Buffalo",
        'newName' => "Elmwood Village",
        'oldName' => "Elmwood "
    ),
);
/**
 * @param string $state
 * @param string $city
 * @param string|array of strings $strings
 * @param array $areas
 */
function process($state, $city, $strings, $areas) {
    // get rid off parameters extra spaces at the beginning and at the end of string
    $state = trim($state);
    $city  = trim($city);
    // find data to replace
    $replaceData = array_reduce($areas, function($carry, $area) use ($state, $city) {
        // if no state selected, then any state will be processed
        // else we're searching only for selected state
        $needToReplace  = ($state === '') ? true : $state == trim($area['state']);
        // the same for the city
        $needToReplace &= ($city  === '') ? true : $city  == trim($area['city']);
        if ($needToReplace) {
            $carry['search'][]  = trim($area['oldName']);
            $carry['replace'][] = trim($area['newName']);
        }
        return $carry;
    }, array('search'=>array(), 'replace'=>array()));
    // if parameter $strings is an array, merge it into the plain string
    $string = is_array($strings) ? implode(', ', $strings) : $strings;
    // do the replace
    $result = str_replace($replaceData['search'], $replaceData['replace'], $string);
    // convert result string into an array, and trim all the values
    $tmpArray = array_map(function($value){
        return trim($value);
    },explode(', ', $result));
    // exclude 'NA', select the unique values and join all into the final result string
    return implode(', ', array_diff(array_unique($tmpArray), array('NA')));
}
// replace any state, any city
$result = process('', '', array(
    '78704 (South Austin), SoCo (S. Congress Ave.), Bouldin Creek',
     'South Congress'
), $area);
var_dump($result);
// replace located only in NY/Austin
$result = process('NY', 'Austin',
    '78704 (South Austin), SoCo (S. Congress Ave.), Bouldin Creek, South Congress',
    $area);
var_dump($result);
result:
string(60) "78704 (South Austin), SoCo (S. Congress Ave.), Bouldin Creek"
string(76) "78704 (South Austin), SoCo (S. Congress Ave.), Bouldin Creek, South Congress"