You shouldn't be allowed to add a "Paid Download" relationship to a CD release, or to any other non-digital release. Here's an example of an edit that would have been prevented, if a check like this was in place: http://musicbrainz.org/edit/17651709

I'm unsure how this should affect releases with unknown medium types.

Alternatively, instead of disallowing this edit, maybe there should just be a warning given instead. This way, you'll be able to add this relationship to releases where the medium has been changed from non-digital to digital that are still waiting on votes.