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 `<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][1].

**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][2]

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í][3] para que lo veas en ejecución.


  [1]: https://regex101.com/r/W1hTTH/1/
  [2]: https://regex101.com/r/XfLuew/4/
  [3]: https://www.ideone.com/4H7kdj