Does the order of the timing constraints make a difference to the Fit?

Order doesn't matter on different paths. They both get applied, and the fitter works on them all.

What's C -> *? Does that meet timing relatively easily?

My experience is the fitter sometimes is not good about placing pipeline registers(although I hear it's being worked on). That being said, overconstraining like this should fix it. I wonder if there's a higher-level topology issue occurring. For example, let's say there are a bunch of DSPs(A) that feed their own B and C and those all merge to one point(or lots of points). In this case, the DSPs are placed in their stripe locations, which are naturally spread out a bit, and so all these locations must converge to a single point. Basically it can't place all these A -> B -> C -> ? and meet timing. Overconstraining pushes around who fails, but at a higher level something always ends up failing. I have no idea, but just a thought as to what may be happening.