No sugar, sure. But wouldn't the diet of common medieval soldiers have be primarily grain based?

Maybe, it depends which crusade I think, and the amount of fiber left in their grain products was much higher. That makes a difference in the adhesive characteristics of the starch to the mouth. Also the insulin response, water retention, and gut health but that is a different topic though linked to gum health for sure.

In pre-modern times, a predominantly grain diet led to tooth decay not only because of starch sticking to the mouth, but also because all grain was stone-milled and the process left tiny fragments of stone in the grain that were abrasive on teeth.