OK I just installed SDV on our 4K computer and I typed some junk which didn't address your issue.
I then re-read what you described (reading comprehension FTW) and tested the toggle from Windowed Borderless to Windowed to Fullscreen (I needed to do it exactly as you described) and after the Windowed to Fullscreen change, it blacked out the TV (which only happens when changing resolutions) and then the image popped up again. But Stardew Valley said it was running at 4096x2160 instead of 3840x2160. My TV is 3840 like all TVs and non-professional monitors (those are the 4096 ones), but it'll apparently display that signal.
So I changed it to 3840x2160, noting what was displayed on the edges of the screen and yes, the sides did shrink in a bit. I think SDV is changing the resolution on your 4K monitor (like it did for me) to something your monitor tries to display, but doesn't quite output properly? Maybe switch to 2560x1440 and then to 3840x2160 and see if that helps?
Also, does your Windowed Borderless look good? Because I can't tell the difference between that and just Fullscreen and that seemed to display properly right from the start. It also seems to perform about the same on a 6 year old Intel NUC with integrated graphics.