How to fix timing issues using the timing assignment options?

I don't agree with the comment that the inverter in the clock will add delay. (It will, but it's an inversion at the IO level that is probably tens of picoseconds at most, which should be noise no matter how tight your constraints are.) But I do agree that using 4 PLL outputs is nice in that you can hand-tweak each clock tree however you like. Since you're using Cyclone and it only has 2 outptus per PLL, you might have to go with the inverted solution.

Internally, I think it can handle 250MHz data flow, although you're not going to be able to do a lot of logic between registers and I would recommend eventually doubling the data path and running at half the rate. This demux can be done inside the FPGA. The Fmax is basically how fast the clock tree can toggle. It has no consideration on how fast the IO can toggle. The problem with IO is that there are a lot of considerations outside of the FPGA(board layout, driving device, etc.) that causes users to do spice simulations on their board. (To be honest, I have little experience in this realm and can't provide a lot more info). But I feel that for the slowest speed grade, you're definitely pushing the limits.

And if cost is a consideration, I believe moving to a more recent family Cyclone II or CIII would probably allow you to go to faster device, assuming the small devices have enough IO.

Finally, you mention that you have a 2ns hold time. This, by itself, isn't an issue since we can phase shift the clocks however we want. But anytime you phase shift the clock backwards to help hold margin, you'll be hurting setup margin. So its the combination of those two requirements that creates a usable "window" for your data to pass between. So once you have your Tsu and Th constraints, and one fails, phase shift the PLL outputs until you can get them to pass. Ideally you want equal positive slack on your Tsu and Th constraints(rather than having one just barely make it and the other make it by a lot). This can help with on-chip variations. Also be sure to run the min timing model. (Not sure if I mentioned it on this thread, but Assignments -> Settings -> Classic Timing Analyzer -> More Settings -> Enable Fast/Slow timing models)

Good luck.