The two instances are only joined by of in English because you chose this in your literal translation. You could have used at or by or to or any other prepositions; prepositions do not transpose simply between languages anyway.

A better literal translation for ménage à trois would be “household with three [people]”. “À deux, à trois, à quatre, à plusieurs, etc.” is common when saying that an action is performed by several people together : « voyager à deux » (to travel together, speaking of two people), “habiter à deux”, …

Coup d’état is a bit different. Originally, a coup d’État was a stroke (as in an important, decisive, vigorous action) performed by or for the state. The 1762 edition of the Dictionnaire de l’Académie française defines it thus:

Un parti vigoureux & quelquefois violent, qu’une République, un Prince, sont obligés de prendre contre ceux qui troublent l’État. On appelle aussi Coup d’État, Une action qui décide de quelque chose d’important pour le bien de l’État.

Later, partly under the influence of a specific event, the phrase came to mean something that changed the government, rather than something performed for the sake of the government.