Pues buscas la "key" (clave) de tu valor "paola" en ese array y lo usas para reasignar su nuevo valor.
Código PHP:
<?
// tu array ($array=$_SESSION['tu_array_de_la_session']; .. o como la obtengas ..)
$array=array("pepe","juan","paula");
// Obtener la clave (indice, Key) de tu elemento que buscas.
// array_keys entrega un array con las coincidencias.
$clave=array_keys($array,"paula");
// asignamos el nuevo valor.
$array[$clave[0]]="nuevo valor";
// Leemos el array para comprobar que todo ha ido bien ...
foreach ($array as $clave => $valor){
echo $clave." --> ".$valor."<br>";
}
?>
Una vez modificada el array .. la registras nuevamente en tu sesión (ya sea $_SESSSION['array']=$array; o session_register("array"); ..)
Un saludo,