Learn English – A question on plural: The A(s) of B and C is (are)…

No, you shouldn't always use the plural.

This is easier to explain after answering your second question:

Yes, the singular 'store' can mean either a stock of materials or a shop.

You should use the plural form when you're referring to something that is plural, whether it is multiple shops or multiple stocks, and the singular when referring to a single thing, whether it is a single shop or a single stock.

Addressing your examples

cupboards for medical stores

A ship would likely have stores of multiple different types of medical materials: at least one store of bandages, at least one store of painkillers, at least one store of antibiotics, and so on. Together, these are the "medical stores". So you use the plural because you are referring to more than one store.

he keeps the ship’s stores

This is like the last one, but all kinds of different supplies, not just medical ones.

crates started arriving at the quartermaster’s stores

This could be ambiguous if you don't know what a quartermaster is.

If it said "the tailor's stores" you would probably assume it meant that crates were arriving at the shops owned by the tailor, as tailors tend to sell things.

Quartermasters are in charge of keeping track of supplies. If you're in the military and you need some shovels to dig a ditch, you might go ask the quartermaster for some. So, the quartermaster's stores are just where the quartermaster stores all the different supplies. The spot where each type of supply is stored is a store of that supply, so we have multiple stores.

They are both grammatically valid, but you have to be aware of the logical context. They are both correct from a strict grammatical perspective, but the first one makes more sense and sounds much more natural in this particular construction. In the context of a comparison ("is better than") the reader needs to know what is being compared. When you use the plural, it sounds like you're comparing one group to another, and it is not clear what the group is.

Typically there is only one man and one woman who would be in a relationship at any given point in time, so the singular sounds better. When you say "no men are better than women at maintaining relationships", it implies there are multiple men involved in the type of relationship in question. Unless the context specifically relates to same-sex relationships or group relationships only, it's confusing and doesn't seem to fit the logic of the proposition.

There might be instances where comparing groups like that might make sense. For example, you could say "no Americans are better than Canadians at fielding a hockey team". The literal implication is that you could select any group of Americans and any group of Canadians and that would always be true, so probably it's logically false, but because people play hockey in groups it makes a little bit more sense. It's the sort of thing a drunk Canadian might say instead of "Canadians are usually better at hockey than Americans."

Where "no men" makes more sense. Outside of the comparison context, it is easier to find circumstances where "no men" makes sense and would be the more natural usage. For example, "no men are allowed into the women's restroom" sounds good and it is clear that you're referring to all men everywhere.

In general the construction "no man" sounds a bit like a proclamation. It is not unheard of for ordinary use, but perhaps more something a king or philosopher would say. So the phrasing "no man is allowed into the women's restroom" is fine in a technical sense, but sounds a little bit like a sign on a royal bathroom (or an English language learner). The phrasings "no man has set foot on Mars" and "no men have set foot on Mars" are both equally valid and natural. Because going to Mars is a grander undertaking, the more dramatic phrasing of "no man has set foot on Mars" becomes more appropriate than when you are discussing a bathroom.