Ok, basically the one you are looking at adds additional functionality to the ALU of the NIOS core. I have never seen a custom instruction shared amungst multiple cores before but it should be doable (but you need some arbitration to prevent collisions).
Is clcok cycle time an issue because this is a lot easier to do using the custom avolon bus interface. (if that sounds good to you let me know and I'll explain it a bit more).
But under usual circumstances you would use the custom hardware in each instance of the NIOS core. The fact that you want to share the hardware would suggest that a couple of extra clock cycles is not going to hurt you so you may want to look at the interface to custom hardware core in the SOPC builder (usually near the top of the core list) since you can do a lot more with it (custom instructions are pretty restricting since they get used with the ALU).
Cheers