Quartus Router Congestion

The PLL is on a global which has dedicated routing, so the fanout doesn't matter. Only 4 pins to the external world? That's impressive.

I think you've just hit a wall and will probably have to remove some logic, which admittedly is not easy. There's no guarantee that a device can be filled that full and always fit. (Although I have seen some impressive thing, like the largest Stratix V GX BB device filled to 99% Logic Utilization which I would have said would never fit.) Two designs of the same Logic Utilization can have significantly different routing requirements, or at least enough to have one always fit and one not fit at all.