Usually I ride my bike 12 miles to and from work, for a total of 24 miles, taking a little under 2 1/2 hours each trip. My bike breaks down a lot, though, so I often walk, taking 4 1/2 hours each way, for a total of 9 hours. This is walking by the side of a country road. Not exactly a flat surface, but not really a hinderance, either.
If they shared my general level of experience and fitness and needed to take the effort and number of hours I work in order to find food and water, I think they could easily do the same 24 miles, even without a day off. So about 720 miles in 30 days.
If they were in better shape and didn't need to work hard to find food, they could do a lot more in a day, but I can tell you from experience it will take a huge psychological toll to do nothing but walk, even if they had someone to talk to. Actually it might be worse if there's other people, because they would slow each other down and get at each other's throats as the monotony settles in.
Also bear in mind you have to work up to walking all the time, even if you're a beefcake. I was already in good shape before starting my whole routine, but walking utilizes just certain muscles. All. The. Time. Even if you're able to put out a lot of power with every muscle of your body, it feels like torture to do the same thing again and again knowing you can't stop for hours. It's totally different from trying to finish a weight lifting routine over a few minutes. You will also feel like someone is hitting your feet with a baseball bat every step you take.
Edit: I also only carry a backpack that weighs ~15 pounds for my walks. If they're carrying a lot more gear it's going to be very difficult for someone who isn't acclimated.