What I've tried:
Setting "4Kp60 HDMI"
I did this in the GUI config application and rebooted. Also tried disabling it and then enabling it in the config.txt and rebooted.
Installing updates
My initial install I didn't install updates during setup. After having issues I installed updates but no luck. I tried another, fresh install, and installed updates during setup but again, no luck.
Setting hdmi_group and hdmi_mode
I tried group 2 and mode 77 for 1600p at 60hz. I also tried hdmi_force_mode after that didn't work but it stayed to what I set it at previously (either 4k@30 or 1080@60).
Setting the resolution
After each attempt, I tried setting the resolution with both xrandr and arandr - I know it wouldn't make a difference but just in case...
xrandr gives me this output:
Screen 0: minimum 320 x 200, current 1920 x 1080, maximum 7680 x 7680
HDMI-1 connected primary 1920x1080+0+0 (normal left inverted right x axis y axis) 1872mm x 1053mm
3840x2160 30.00 + 30.00 25.00 25.00 24.00 24.00 29.97 23.98
4096x2160 30.00 25.00 24.00 24.00 29.97 23.98
1920x1080 60.00* 60.00 50.00 59.94 30.00 25.00 24.00 29.97 23.98
1680x1050 59.88
1600x900 60.00
1280x1024 75.02 60.02
1440x900 59.90
1366x768 59.79
1280x800 59.91
1152x864 75.00
1280x720 60.00 60.00 50.00 59.94
1024x768 75.03 70.07 60.00
832x624 74.55
800x600 72.19 75.00 60.32
720x576 50.00
720x480 60.00 59.94
640x480 75.00 72.81 66.67 60.00 59.94
720x400 70.08
Display: Samsung UE40NU7120
I believe the display might be the problem as it's a TV. But it's a fairly recent one and handles 4k@60 from my PC.
HDMI cable: https://www.amazon.co.uk/dp/B014I8TVLI/ref=twister_B01AM5SOUK?_encoding=UTF8&psc=1
I don't have another micro HDMI so I can't test that. This claims to support 4k@60hz though. I've tried both ports on the pi too.
I've seen a couple of posts on other sites about this with no fix. It's hard to search for though as every link is discussing the feature.
Update
I've tried this on other 4k displays and it works fine at 60hz. It appears to be a problem with this particular display.
Update 2
Semi-related for people that might come across this looking for answers, I've no longer got the Pi 4, but I had a similar issue with my PC with an RX 580 GPU and the same display. This Ask Ubuntu answer seems to have resolved it for me. As I said though, no Pi 4, so I can't test it there.