Have you checked for software updates from the App Store since the first time you connected the expensive dongle for HDMI output?
- After connecting for the first time there is often a firmware update that is necessary for the dongle to function correctly
You could try a PRAM reset on the shiny new MacBook Pro 13" (if you haven't already).
You could try booting into - and back out of - Safe Mode.
Have you ensured the expensive dongle for HDMI output isn't defective?
- You could test with a different display like a TV to see if the issue still occurs. (And if you happen to have a second Mac other than the shiny new MacBook Pro 13" hanging around for testing, that would narrow it even further!)
Have you ensured that the expensive dongle for HDMI output isn't incapable of supporting such a high resolution?
- To test you could try lowering the resolution from 'System Preferences > Displays > Display'
Have you tried installing/reinstalling the shiny 4k monitor drivers?
If issue persists, I have a few more questions.
Last but not least, a little shiny bird told me that 4K displays have to be configured for 60Hz to function correctly. If it's being forced into any other refresh rate (like 30Hz), that could be the problem.