To be fair, there were no adventurer's guild in real medieval ties, and no powerful monsters, only bandits in forests, so it should be easier and common enough for this world's adventurers to travel to different place in search of better opportunities. They would be armed enough to travel safely, and had a guild structure in new town to which they could adapt, and like for hunters, it would be somewhat normal for them to search better hunting grounds.
And, IIRC, quite a few guilds also had apprentices move around in different towns to learn their trade. Though in this case they would be also part of existing social structure. There were also traveling entertainers, like Gypsies (though they had they own society and they were also treated with deep suspicion by the villagers), and in Japan there were for example blind travelers playing biwa, at some point even blind women singers called goze could also travel with them, but those also had their own society with own rules and were treated more like travelling pilgrims or monks, which protected them - yeah, in most cases traveler should be part of existing institution or society that could protect them from being mistreated. There were still common cautionary stories in those times about poor traveler mistreated by hosts who turned out to be lord or god in disguise, but those also meant that such mistreatment was common enough to warn against it.
Seems to me that our MC should try to get someone in previous time to vouch for him, even if by letter, though he had best reputation in the town where he punched local lord and escaped, and ... did he kept good rep when leaving any other place? Even the fishing village arc ended in fake hostility, and no one would care about some village. Yeah, he's fucked.
