con str_replace :
str_replace
$str = str_replace("\n", '<p>', $str);
y como mejor alternativa usando la constante que define "Fin de línea" PHP_EOL :
$str = str_replace(PHP_EOL, '<p>', $str);