You are correct, HD is really the resolution of the display. Say 1080p vs. 1080i or 720p.
So they can set and send at an HD resolution but still compress the signal which always causes some loss of data. For the paid Movie Channels in HD or the sponsored channels like Hallmark, they compress less so it will look better.
As of yet, I have not heard of any compression algorithm for 4K programming, but I'm sure that it will come. But 4K, instead of resolution, is a data transfer rate. So, the would at least have to transfer data at 4K even if your set supports 4K video. That is why you need to by the newest special HDMI cables because the older ones just can't handle the data rate. As said above, that's probably why there is only 1 4K channel in the lineup right now.