Your main question has been well answered by Penelope and in the article linked by brianpck: when there is a coordination of more than one subject, the verb can agree with the entire coordination or just with the nearest member. So I'll address your other questions, about particles.
First, a general point about translating Greek particles: don't get too wedded to one-to-one translations, like thinking that γε always has to be translated as "at any rate". Particles are too nuanced and context-sensitive for such an approach to work, especially as in many cases the English translations that are traditionally offered are themselves rather vacuous: e.g. you may have been told that μήν is to be translated "indeed", but what does the English word indeed actually mean outside a specific context? Not to mention that the same indeed also gets offered up as a translation of δή or γε, which have completely different functions from μήν.
Let's look first at the γε in ἐκείνοις γε. The function of γε is most often as follows: it picks out one entity out of a set of possible entities in the discourse, and says that the current predication should only be assumed to hold of that particular entity; it may or may not hold for the others -- γε is noncommittal on that point. The entity γε picks out is the word immediately preceding. So in this case, ἐκείνοις γε means that the predication "we have given music and athletics to X" should at this point only be assumed to hold when X = ἐκείνοις, that is, "the men in the ideal state". This is because Socrates has not yet discussed the tasks of women; he's going to go on to say that the same predication should be extended to the women too, but that hasn't happened yet. In terms of translation, "at any rate" gets the point across but is a little cumbersome; more naturally in English one would express this type of meaning with intonational emphasis and possibly fronting the phrase to the beginning of the clause: "Now, to the men, we gave athletics and music."
Now for μήν, which is more complicated. I recommend the discussion in Denniston's Greek Particles (both for μήν specifically and for other particles). A few relevant points:
- In Attic prose μήν usually occurs with a negative, as in οὐ μήν; the positive use, however, is typical of Plato's later works.
- (This is not in Denniston, but is my sense of the basic function of μήν.) What μήν often does is to mark a statement as something that the speaker is certain of and is willing to fight for, so to speak -- that is, even if you, the hearer, don't agree, I'm prepared to argue for the truth of the μήν statement. In this it's different from δή, which usually assumes the hearer agrees with or shares the attitude being expressed.
- Out of this basic function (this is now Denniston's "progressive" use) arises a use of μήν to introduce a new point in an argument, but one which is based on another point that was already made and settled. This arises from the previous function because the speaker is expressing certainty about the previously settled point, which he is now going to use as a foundation for a new argument. A translation like "well" or "now" will often work -- the Perseus translator chose the latter.
(Finally, I have to disagree with Penelope's suggestion that καί in this sentence may be the adverbial καί meaning "also" or "even" -- it can only be a connective "and", conjoining the two nominatives; syntactically the sentence cannot do without a coordinator at that point.)