There's a difference between the two choices. In the first one, "They would travel..." and "they'd march..." are independent clauses. In the second one, the omission of "they'd" makes it "They would travel ... and march...", a single sentence with a compound predicate.
Independent Clauses
They would travel by ship to Glaucon’s holding of Phoclydies, then they’d march across land to Ceolliune-Callat.
Definitely a comma splice.
Correct? Unnhh, well, ... With "then", it seems to be a little less egregious than the usual comma splice. So, I suppose using this could be a valid judgment call as long as you are aware of what you're doing.
They would travel by ship to Glaucon’s holding of Phoclydies, and then they’d march across land to Ceolliune-Callat.
Adding a conjunction. A classic solution for independent clauses. (Sorry, Uncle Jim!)
They would travel by ship to Glaucon’s holding of Phoclydies. Then they’d march across land to Ceolliune-Callat.
Two separate sentences. Another correct choice, although I might make the second sentence "They would march.." for the sake of parallel structure.
They would travel by ship to Glaucon’s holding of Phoclydies; then they’d march across land to Ceolliune-Callat.
A semicolon also works, when the ideas are more closely related than separate sentences would serve.
Compound Predicates
They would travel by ship to Glaucon's holding of Phoclydies and then march across land to Ceolliune-Callat.
Correct. A comma is
not used for a compound predicate. (Unless there are more than two parts; then you have the listy thing. "He hopped, skipped, and jumped.")
They would travel by ship to Glaucon's holding of Phoclydies and march across land to Ceolliune-Callat.
I disagree with brer. Grammatically, it's correct, but the meaning is wrong. Removing "then" to leave "and" standing alone implies the actions are simultaneous, which is clearly impossible in this case.
They would travel by ship to Glaucon's holding of Phoclydies and would march across land to Ceolliune-Callat.
Again, grammatically correct, but the same problem of simultaneity. To make it worse, this one just sounds clunky.
Other Possibilities
They would travel by ship to Glaucon's holding of Phoclydies before marching across land to Ceolliune-Callat.
My terminology is reaching the shaky point, but I think "marching across land..." is a participial phrase, which is in turn the object of the preposition* "before". Whatever it's called, no punctuation is needed.
After traveling by ship to Glaucon's holding of Phoclydies, they would march across land to Ceolliune-Callat.
Same as above, but because the prepositional* phrase comes first, a comma is needed.
*I did some browsing and found
this, which says "before" and "after" in those last two examples are subordinating conjunctions, not prepositions. But it confirms my comma usage for them. The same site also has a nice
discussion of comma splices, specifically covering "and then".
(It sure would be nice to be able to quote quoted text without having to copy-and-paste it in. I've been on other forums, I
think using this same software, where quotes automatically nested. </grumble>)