I would be glad if anyone could help me how to translate the name "Church of the Virgin Mary" or at least how to place "of the" in the sense of "belonging in patronage" in such contexts? Other examples that I would struggle with would be "Covent of the Holy Virgin" or "St John's Covent". Would it be "de" as in "Ecclesia Cathedralis Nostrae Domina de Immaculatæ Conceptionis" for such examples?
There are two main ways to do this. One is the earlier usage, from Classical Latin, and the other is the later usage, from Vulgar Latin.
You actually provided an example of both!
Ecclesia Cathedralis Nostrae Dominae de Immaculatae Conceptionis
Cathedral of Our Lady of the Immaculate Conception
The older/Classical way is to use the genitive case, a special ending on the possessor. "Our Lady" would normally be nostra Domina; "of our Lady" is nostrae Dominae.
The later/Vulgar way is to use the preposition de, which replaced the genitive case in the Romance languages—so it'll look familiar from Italian, Spanish, French, and so on. This isn't good Classical style (in Classical Latin, de means "down from" or "concerning", not "of") but it's very common in later Latin. In fact, your example actually uses both together: immaculatae conceptionis is in the genitive, and it's preceded by de.
As a classicist, I prefer the genitive, and I believe the Vatican does as well. Thus, the Church of the Virgin Mary would be Ecclesia Virginis Mariae. Similarly, your other examples would be Conventus Virginis Beatae, and Conventus Sancti Jo[h]annis.