While I'm not using a 4K HDTV or monitor, I have a AMD 7950 in my 2008 Mac Pro 3,1. It's advertised to drive 4K monitor. While it's no longer in production, you can find them on eBay. I got a PC version (for $100 USD) and had MacVidCards update the 7950's BIOS with the Mac compatible EFI VBIOS. He can do that with most PC graphics cards that use the nVidia or AMD Reference Card configuration which Apple uses for it's Mac graphics cards.
IIRC, you'll get 4K through the mini DisplayPort connectors on the 7950. I don't think you'll find an older, affordable graphics card supporting 4K via the HDMI connector unless it's one of the nVidia 980 or 970 cards. But, to use the newer nVidia cards, you'll have to upgrade to Yosemite (10.10) and use the nVidia Wed driver. AMD R9 series cards that support 4K are not support, yet, in Apple's OS X. Anyway, unless you can make a 7900 series card or (maybe) a nVidia 680 card work with your HDTV/monitor, you'll be forced to upgrade to Yosemite to find a card that will support 4K. BTW, I'm running Yosemite on both my MP3,1 and MP5,1.
With a graphics card that supports 4K, you'll need two PCIe PSU cables to hook up to the MP4,1's motherboard. If you don't get the 7950 card, make sure you understand the card's power requirements as some of the nVidia 680 and 900 series cards could require an external PSU since the MP3,1's PCIe PSU motherboard connectors are limited to 75 watts each.
I'd also recommend the graphics card sticky thread on graphics cards in the MacRumors Forum's Mac Pro forum section.
Good luck!
Reference Links:
Sapphire 7950:
http://www.newegg.com/Product/Product.aspx?Item=N82E16814202031
MacVidCards 7950
GPU Hierarchy Chart - Best Graphics Cards For The Money: March 2015
MacRumor's Mac Pro Forum Seciton's Frequently Asked Questions About NVIDIA PC (non-EFI) Graphics Cards