If you look at the geography it's not totally surprising. Cyrene is cut off from Carthage in the west and Egypt in the east by inhospitable desert, making over-land communications very difficult. Crete is actually closer to Cyrene than anything else in north Africa, and in fact Crete is closer to Cyrene than to the major inhabited regions of mainland Greece. It therefore makes geographical sense to link them together. Neither were populous or troublesome enough to justify separate administrations, so in some senses linking them together is an act of administrative efficiency. I don't know where Wikipedia gets the idea that the provincial capital was Gortyn - it might have been the centre of Roman administration on the island, but as far as I'm aware the provincial governor was resident in Cyrene.

The two were culturally linked, as well as geographically. Cyrene was built by Greek colonists in the sixth century BC, and remained culturally and politically Greek throughout Antiquity. In that sense, linking Cyrene with another predominantly Greek region, i.e. Crete, was sensible in terms of the governors and other Roman administrators facing similar challenges and problems when running the two areas.