Eu iria trapacear ao invés de tentar descobrir um regex.
Pesquise a tag que você não deseja alterar e substitua-a por uma string exclusiva:
Search: "<p class="nav">" Replace: "***xxxxxx***"
Em seguida, faça sua operação em todas as outras tags <p>
e inverta a alteração original:
Search: "***xxxxxx***" Replace: "<p class="nav">"