Samsungs ultrawide c34f791 had horrid flicker when choosing so-called ultimate engine freeysnc range 48-100 but apparently with vega or perhaps due to vega drivers the flicker is almost gone. It still flickers on slow motion camera but the flicker is no longer visible for humans or at least noticeable flicker is almost gone (apparently, though today I read that somebody still has flicker issues with this monitor + vega 56 so I have no idea who to trust but gamernexus did a video showing that with vega the flicker is much improved).
Try freesync with new AMD divers with y9our old r9 390, see if it helped.
For 4k reolution and if freesync does not really work then I would go for 1080Ti, its just enough to get 60fps in modern titles.
If 1080Ti is too expensive, then yes vega 56 seems to be better choice.
Btw vega 56 standalone cards are back in stock.