I understand coming as he did to be a kind of do-emphasis with ellipsis of the infinitive: coming as he did [come].
Compare the emphatic here:
As you do know, Mr O'Hope, this class starts at 9AM on the dot.
as could be paraphrased "in the way (that), in the manner (that), like".
as he did is an adjunct to the predicate which also identifies the subject of the predication. Without it, there would be a non-finite clause without a subject:
Coming from the senatorial class...
and then a possible parsing hiccup when we reach it, the grammatical subject of was in the main clause, which stands in for the that-clause, which supplies the idea-content for it.
but with as he did, there is a clearer connection between the non-finite clause and the matrix clause: he = Caesar.
We can turn the sentence around and eliminate the dummy it:
That Caesar would serve as he did in both the army and the Senate was
only natural, for he came from the senatorial class.
And in that rewrite, as he did = as he did [serve].
The that-clause without as he did would not declare a fact about Caesar. It declares only a possible idea; it is only a nominal, not a predicate, hence the need for as he did.
That everyone on the planet should have food to eat ...
does not contain a predicate. That turns it into a nominal, which can be the subject of a predicate.
That Caesar would serve — as he did in fact serve — in both the army and the Senate was only natural, for he came from the senatorial class.
Without as he did the that-clause could be paraphrased as
That Caesar was expected to serve in both the army and the Senate ...