con `str_replace` :

    $str = str_replace("\n", '<p>', $str);

y como mejor alternativa usando la constante que define "Fin de línea" [PHP_EOL][1] :

    $str = str_replace(PHP_EOL, '<p>', $str);


  [1]: http://php.net/manual/es/reserved.constants.php