<div>
    Lorem ipsum dolor sit amet
    <div>
        Lorem ipsum dolor sit amet
    </div>
    <div>
        Lorem ipsum dolor sit amet
    </div>
    <div>
        <div class="media_embed">
                <div style="xxx">
                    <div style="xxx">
                        <div style="xxx"></div>
                    </div>
                </div>
        </div>
    </div>
    <div>
        Lorem ipsum dolor sit amet
    </div>
</div>

<p>
    Lorem ipsum dolor sit amet
    <p>
        Lorem ipsum dolor sit amet
    </p>
    <p>
        Lorem ipsum dolor sit amet
    </p>
    <p>
        <div class="media_embed">
                <div style="xxx">
                    <div style="xxx">
                        <div style="xxx"></div>
                    </div>
                </div>
        </div>
    </p>
    <p>
        Lorem ipsum dolor sit amet
    </p>
</p>

<?php
      $embeds= $dom->getElementsByTagName('div');
      foreach ($embeds as $embed) {
          $class = $embed->getAttribute('class');
          if ($class == "")
          {
            $link= $dom->createElement('p');
            $embed->parentNode->replaceChild($link, $embed);
          }
      }
?>

<?php

$html = '<div>
    Lorem ipsum dolor sit amet
    <div>
        Lorem ipsum dolor sit amet
    </div>
    <div>
        Lorem ipsum dolor sit amet
    </div>
    <div>
        <div class="media_embed">
                <div style="xxx">
                    <div style="xxx">
                        <div style="background-color:red;"><p>Rojo</p></div>
                    </div>
                </div>
        </div>
    </div>
    <div>
        Lorem ipsum dolor sit amet
    </div>
</div>';

$doc = new DOMDocument();
$doc->loadHTML($html);

$nodeList = $doc->getElementsByTagName('div');

// Convertimos la "nodeList" a arreglo
// de lo contrario al pasar "divs" hijos a un "p"
// se pierde la referencia en la "nodeList"
$divs = iterator_to_array($nodeList);

foreach ($divs as $div) {

    // Si no tiene atributos
    if (!$div->hasAttributes()) {

        $p = $doc->createElement('p');

        // Trasladamos todos los hijos del "div" al nuevo "p"
        while ($div->hasChildNodes()) {
            $p->appendChild($div->firstChild);
        }

        // Reemplazamos el "div" por el "p"
        $div->parentNode->replaceChild($p, $div);
    }
}

echo $doc->saveHTML();

$html='<div>Lorem ipsum dolor sit amet</div>
<div>Lorem ipsum dolor sit amet</div>
<div>Lorem ipsum dolor sit amet</div>
<div class="media_embed"> </div>
<div style="xxx"></div>
<div style="xxx"></div>
<div style="background-color:red;"><p>Rojo</p></div>
<div>Lorem ipsum dolor sit amet</div>';
$regex = '#<div>(.+?)</div>#s';
$result = preg_replace( $regex,
    '<p>$1</p>',
    $html
);
echo $result;

<p>Lorem ipsum dolor sit amet</p>
<p>Lorem ipsum dolor sit amet</p>
<p>Lorem ipsum dolor sit amet</p>
<div class="media_embed"> </div>
<div style="xxx"></div>
<div style="xxx"></div>
<div style="background-color:red;"><p>Rojo</p></div>
<p>Lorem ipsum dolor sit amet</p>

$('div:not([class])').contents().unwrap().wrap('<p/>');