Pode não estar claro na documentação, mas rewrite diretivas no bloco server são avaliadas sequencialmente antes da pesquisa por location para processar o URI.
Portanto, a instrução " rewrite ^/p/(.*) ... " será avaliada antes da instrução " location ~ ^/p/1234 ... ", independentemente da ordem dessas duas declarações.
Você pode converter suas declarações rewrite em location blocks ou vice-versa.
Por exemplo:
rewrite ^/p/1234 /p/5678 permanent;
rewrite ^/p/(.*) /mm5/merchant.mvc?Screen=PROD&Product_Code=$1 break;