It's a random encounter. The hired thugs appear after you steal an item or murder someone, even if you weren't seen. They often show up early in the game and are difficult to defeat, as you already discovered - I usually run for my life when I see them

I don't think it's connected to the axe, you probably just picked an apple or something and it was tagged as stolen. Check the statistics tab, I think it counts the number of stolen items and assaults.