Why does this design not fit and how to reason about congestion

Altera's estimation can be very wrong at times, especially on Arria 10.

If your design is failing during placement, then it means the design is too big to fit on the FPGA, even though in my experience, AOC's DSP usage estimation is generally correct.

If, however, your design is failing during routing due to congestion, with a an area utilization that is not relatively high, then there isn't much that can be done about it except redesigning the kernel. On Arria 10, since OpenCL uses Partial Reconfiguration through PCI-E by default, routing fails very regularly due to routing congestion in the region that connects the static block to the dynamic block (I have encountered this far too many times to count). I have never gone over 60% DSP utilization on Arria 10, though (logic and RAM are usually over-utilized long before DSP in my experience), so that might also be a contributing factor.

On Stratix V, however, I have encountered routing failure due to congestion only a few times, and that was because my design was bad (too many non-coalesced reads and writes from the same local buffer).

Can you provide the quartus_sh_compile.log and also mention your target device and the version of Quartus/AOC you are using?

P.S. Your first kernel looks relatively straightforward and data parallel; you might have better luck if you implement it as NDRange. In particular, spatial blocking using local buffers that are implemented as standard multi-ported memory buffers on the FPGA (in contrast to, for example, shift registers) seem to work better in NDRange kernels in my [limited] experience.