{Progenitus} can it be countered? Or does it have protection from the spell countering it?
Progenitus itself can be countered while it is on the stack. But once it becomes a permanent on the field it cannot be targeted, dealt damage, enchanted, blocked etc. While it is a spell on the stack it is counterable like (almost) any other spell.
Note that {mistcutter hydra} still needs the can't be countered clause even though he has pro blue. Protection effects are basically only relevant for permanents. I guess a player could also gain protection but otherwise it only matters while permanents are permanents and therefore on the battlefield.