How to improve Fmax for SOPC System?

You said your problem is within the NIOS.

Doubt you will get 40% more performance by changing Quartus-II settings.

Suggest you try changing the NIOS settings as well.

Change mode, I have seen a simple fast mode NIOS compile to better fmax than economy, and the other way around as well. Try things such as reducing or turning off Cache, reducing the debug complexity, eliminate special features such as custom instructions etc. As a last resort you could run the NIOS at a slower clock rate than the rest of the design and use clock domain crossing bridge(s).