I would like to check some information regarding the cables you have tested; by any chance do you know the brand and model of them? I would like to confirm if these are compliant to the Intel® NUC specification and also to check if they are high quality cables.
This link maybe helpful: HDMI :: Consumers :: Buying Guide
This is one of the HDMI cables I tried: HDMI Cable 6ft - HDMI 2.0 (4K) Ready - 28AWG Braided Cord - High Speed 18Gbps - Gold Plated Connectors - Ethernet, Audio Return - Video 4K 2160p, HD 1080p, 3D - Xbox PlayStation PS3 PS4 PC Apple TV
This cable and other HDMI cables I tried with other computers and the same TV give 4K picture without any issues.
From my NUC, I found that I can get a 4K output using USB-C. That works well. However, it would be nice to be able to use USB-C for other things and get the video through HDMI.
I am still not able to do that.