> Is there an online source for the diet of Roman soldiers?
A quick search reveals that "The Roman soldier's diet was mostly grain: wheat, barley, and oats, mainly, and also spelt and rye."
Pretty much the antithesis of paleo.
However, some controversy exists regarding how and when meat might have entered the picture for the soldiers. Marching with a bag of grain would be far easier than trying to get or keep meat during extended campaigns. But once a campaign was complete, and spoils were taken from raided villages, meat might have been generously eaten.
Interesting reading
http://ancienthistory.about.com/b/2007/05/29/roman-military-diet.htm