Well, Ultra-wide means you're not really at 4K, which is defined as 3840x2160, but instead at 3840x1600.
That said, I think that a 3440x1440 resolution would be just fine for gaming. And, the GPU won't have to work as hard to get higher frame rates. After all, the more total pixels, the more work the GPU has to do.
There are plenty out there - but because monitors are so subjective (what my eyes like isn't necessarily what your eyes like), I would STRONGLY suggest trying to find a place that keeps a lot of monitors on display. See what feels comfortable and feels right for YOUR eyes.