Tienes varias alternativias.
La mejor opción sería utilizar un parseador de HTML.
Dicho esto, si quieres seguir usando expresiones regulares, tienes estas dos opciones:
Opción 1:
Utiliza la siguiente expresión regular <div>([^<]*?)<\/div>
y reemplaza por $1<p>$1</p>
Esta es la opción más sencilla, pero sólamente te funcionará en el caso de no tener tags html anidados y también con la condición de que dentro del texto no encuentres el caracter '<'.
Es decir, estos dos casos no funcionarían:
<div> <span>hola</span> </div>
<div> 3<4 </div>
Pero sí que funcionaría con el ejemplo que has puesto. Demo.
Opción 2:
Este método lo utilizaremos para evitar la limitación anterior. Mediante un bucle y una expresión regular recursiva, iremos haciendo sustituciones.
La expresión regular es la siguiente <div>((?:<div[^>]*>(?1)<\/div>|[^<]*|<(?!div))*)<\/div>
(flags: m,s,i) y reemplaza por <p>$1</p>
Demo
Sin embargo esto sustituirá un único nivel en caso de encontrar etiquetas anidadas. Por ejemplo si tu entrada es:
<div><div>hola</div></div>
Lo cambiará a
<p><div>hola</div></p>
Con lo que deberás ejecutarlo una vez más para obtener:
<p><p>hola</p></p>
Básicamente repites la sustitución hasta que el string anterior sea igual al nuevo (significa que no hay nada adicional por reemplazar)
Aquí tienes un ejemplo montado con php:
<?php
$prevhtml = '
<div class="foo">
<div>FOO</div>
<div class="bar">
<div>BAR</div>
</div>
<div>FOOBAR<div class="foobar"></div></div>
<div class="bar"><div><b>BAR</b></div></div>
<!-- para este caso, deberás ejecutar preg_replace
hasta que no haya nada nuevo por reemplazar -->
<div><div>foobar</div></div>
</div>
';
$newhtml = '';
while($newhtml != $prevhtml) {
if (!empty($newhtml)) $prevhtml = $newhtml;
$newhtml = preg_replace(
'/<div>((?:<div[^>]*>(?1)<\/div>|[^<]*|<(?!div))*)<\/div>/smi'
,'<p>$1</p>'
,$prevhtml);
}
print $newhtml;
También tienes el código aquí para que lo veas en ejecución.