While it's never going to cause this kind of gross pollution, use regular gas. Higher octane gas can hurt emmisions.

Log your o2, your probably going to find it either dead, or reporting full rich at idle. If it's not dead, start looking at the fuel injection system, MAF readings, etc. Something's giving cause to pump fuel in. Or failing that, it's not burning.

High NOX is often an EGR valve getting stuck, failed or a cat on the way out.

A busted FPR could certainly be increasing fuel pressure far outside what the ECU can account for, but you'd probably have other serious driveability issues as well as that.

If your o2 test's good, and maf readings are within reason, I might do a quick fuel pressure check, but it's likely your going to find your trouble before getting to it.

Plugs and wires can't hurt, but would need to be way into miss-fire at idle territory to cause this kind of trouble. And lastly, the cat is often not to blame, but running very rich for a long time can really take it's toll and plug them up with carbon rendering them pretty in-effective.

Paul