Tate no Yuusha no Nariagari

[KrayZ33]

Well, it's not like Naofumi is traveling through the whole country.

They could in theory be 5 small towns apart, which by foot would require a day of travel. I wouldn't call that "far and wide". So information and rumours spreading depends on the frequency of merchants passing by. The merchant said something along the lines of "you have a reputation in this area" after all and they keep traveling back into the capital.

As for the skills, it didn't seem like he had to invest a lot of time to learn a skill, might have learned all about it on the same day - they live in a game world with game mechanics after all.

He's certainly not taking any days off, but it doesn't require several months to just travel around and trade when you have the fat birb around.
He barely leveled up too