I’m limited more by stride length and cadence than I am by ‘effort’ or fitness, and I’m around the average height for older populations (a bit short by modern standards) at 5’6".
I seriously doubt that exceeding 7.2km/h average/flat on made surfaces is practicable. On the other hand I maintain 6.5km/h or a little over all day 55km+ on footpaths, ancient greenways and other semi-prepared surfaces… which would approximate the conditions expected on our in-game paths and roads.
I have a little bit more ‘stretch’ to permit around 8km/h when walking on made surfaces downhill, but this is difficult to maintain on more variable surfaces and drops off on very steep slopes. Uphill… I have plenty of strength and fitness to maintain my 6.5km/h speed up to around 16% grade indefinitely, and 25% for short bursts. Steeper slopes up to 40% are walkable, but speed falls off rapidly.
I’ve never met anyone while out who has been walking as fast as this*, so averages are probably a fair bit lower. It is possible that a person could walk faster while retaining a normal walking gait, but only if they were noticeably taller, & with longer legs.
*and sometimes overtake joggers…
My shoes are only ‘store bought’ and not as good a match to my feet as the simpler whole grain hand made boots I had for a while a decade or so ago. This factor may work in the favour of the period character so long as he can keep them in good repair and replace/repair when worn. Still I don’t often get any kind of blister or other foot problems, unless walking for hours in wet weather.