What frequency do you run Nios at?

167MHz is doable on the Nios embedded eval kit (NEEK). It could go higher but then you would be running the external memory out of spec. That's a 6 speed grade so on the slowest speed grade of 8 I would expect the fastest would be around 120-130MHz assuming you architect your system for frequency instead of latency.

Yes custom instructions can become part of the critical path. You can determine if they are by showing the complete timing path and checking to see if the custom instruction logic is part of it. You should see the start and end of the path being the Nios II pipeline (or the on-chip memories that form the CPU registers) with the custom instruction somewhere in between. If achieving a high frequency is important and the custom instruction is in the critical path then consider pipelining the custom instruction.

Of course it doesn't make any sense to look into any of this unless you have constrained your design. If you haven't then I recommend that be your first step so that your I/O timing can be traded off with the on-chip timing properly by the fitter and timing analysis. I recommend using Timequest for this as it will give you better results than the classic timing analysis tool.