[RPG] How does maintaining a Concentration spell work

Your question is indirectly addressed by these tweets from Jeremy Crawford:

As DM, I'd rule that you can't control a delayed blast fireball while inside an antimagic field. ... You could regain control when neither you nor the bead was in the antimagic field.

Note that he's assumed the Delayed Blast Fireball spell doesn't get suppressed just because the caster is inside an Antimagic Field; however the intention (the rules are silent on this) is that you can't control a spell while you're in the antimagic field or while the spell is suppressed.

RAW, only the last hex would give disadvantage

This requires some close reading of the PHB and some interpretation, but I'll quote the relevant section for reference here:

The effects of different spells add together while the durations of those spells overlap. The effects of the same spell cast multiple times don't combine, however. Instead, the most potent effect - such as the highest bonus - from those castings applies while their durations overlap. (PHB p. 205)

Note that this has actually been errata'd:

Combining Magical Effects (p. 205). In the first paragraph, the following sentence has been added to the first paragraph: “Or the most recent effect applies if the castings are equally potent and their durations overlap.”

And now, the hex spell:

You place a curse on a creature that you can see within range. Until the spell ends, you deal an extra 1d6 necrotic damage to the target whenever you hit it with an attack. Also, choose one ability when you cast the spell. The target has disadvantage on ability checks made with the chosen ability. (PHB p. 251)

If we look at the hex description, we see two distinct effects. One affects you, the caster, and causes you to deal more damage on attacks against a specific target. The second affects the target, and grants disadvantage on certain ability checks (I feel obligated to point out it doesn't affect saving throws). Note that the rules on combining magical effects applies to "effects of the same spell", not the entire spell itself. Thus, we can make the assumption that only the effects that are trying to combine will have to "fight" each other. As mentioned in this answer on hunter's mark, the first effect of dealing damage only affects the caster. The multiple castings do not stack and everything works out without conflict. However, the second effect affects the target, and therefore multiple castings will interfere with each other. As mentioned in this answer on similar spells, the most potent spell would take precedence even if the exact mechanics of the effects don't "stack" (i.e. even if the warlocks target different abilities).

What does this mean for your scenarios?

Scenario 1:

Each of the warlocks cast hex, targeting Wisdom checks (again, this won't affect the paladin's saving throws). The first effect, that of dealing extra damage, applies to each of the warlocks. The second effect however cannot stack, and only the most potent applies. Since they are all of the same potency, we rely on the errata to determine that whichever warlock happens to cast last has their spell go through. Dealing with simultaneous effects is completely DM dependent; some resolve speed ties through Dexterity bonuses, others go around the table clockwise, others allow the players to determine who goes first, etc. As V2Blast pointed out, Xanathar's Guide to Everything (p. 177) suggests the players decide. However the order is determined, only one of these warlocks is actually imposing disadvantage on Wisdom checks. This doesn't mean that the other warlocks' hexes are dispelled though - they simply have no effect.

So, the paladin breaks one of the warlock's concentration. Now, there are two hexes affecting the paladin. If the previously 'most recent' hex was the one that was broken, the next 'most recent' hex applies, since a dispelled hex is certainly less potent than an active one. It doesn't really matter whose hex is still up, since they all picked the same ability. The paladin still has disadvantage on Wisdom checks, and the unharmed warlocks still have damage bonuses on their attacks.

Scenario 2:

This one plays out exactly as above; the last hex takes precedence. Again, which one this is is up to the DM.

Hopefully this answers your question! I made sure to look around the internet before trying to give a RAW answer and there seems to be lots of confusion around similar spells. Perhaps in the next edition we'll have more clear definitions of words like effect and combine so we don't leave everything up to DM interpretation.