What are "the fates of men" on which the wanderer reflects? Why might his own experience lead him to such brooding thoughts?
Fate has three common definitions which are (1) something that unavoidable happens; (2) a universal principle that orders the happening of events; (3) death destruction and ruin. In Line 5, "Fate" is used in accord with the second of the above definitions. In The Wanderer, The word "fate" appears four times, twice early on (lines 5 and 15) and twice in the third section (Lines 101 and 108). The third context in which fate is used is when warriors of a kingdom behind a "wondrous high wall" (depicting a wealthy and powerful kingdom) are overtaken by enemies at night with "ash-spears" that are "corpse-hungry" reduce the once famous warriors to corpses--a great realm is destroyed and lost, in the same way that the Wanderer is himself lost.
Immediately after the battle description, the Wanderer is lamenting the snowstorm the "dash on" at the time of the battle he just finished describing. He says the storm attacks and "binds all the ground" and is accompanied by dark when "night-shadow blackens" while hailstorms drop angry assaults on humans. From this we derive the image that warriors in the battle who might have survived were overcome also by the storm and nothing survived.
The context of the fourth use of fate follows the statement that "All is the earth-realm laden with hardship" (Line 107) and seems to accord with the first definition of "fate." This hardship of natural disaster is called "fate of creation," which is easy to understand considering all the natural disasters across the world in the last few years, from Katrina to Haiti. The Wanderer has described two kinds of fate. The first is man-versus-man elements of fate, like war and death, and the second is the natural world at odds with humans' survival.
The Wanderer goes on to list more instances of fate. One is that wealth ("goldhoard") passes, perhaps is lays hidden and unused after a battle's destruction or perhaps it lies useless after all are buried in a winter raging storm so fierce that it is like a "stone-cliff." Other listed instances of fate are that friendship dies, family "kinsman" die, life on earth ("earth-frame") becomes worthless and meaningless.
Earlier mentioned instances of fate that are the realities of the Wanderer's experience are the loss of a king and leader (kings distributed the plunder taken in battles and so were like employers in that they gave gifts of wealth (from the plunder) for the warriors to live by), being the sole survivor, seeing other kingdoms defeated and ruined, lamentable memories and dreams. The reason the Wander broods on fate is because he has found a hard fate to live through being a sole survivor of his kingdom's destruction, a circumstance that cast him into an exile in which he is fruitlessly (unsuccessfully) searching for a new kingdom that will accept him and that he can embrace. But all he finds is more destruction everywhere he turns and he is still alone with only sorrowful dreams and memories that make life on Earth worthless to him. As the Wanderer says in Line 15, "Weary mind never withstands fate."
The "fates of men" in this context is simply whatever turn of events happen to people. It is the idea that people are not in control of their own lives and that outside forces control them.
The wanderer's own experience has made him feel out of control. He has had to wander around the world without friends or protection or a leader. This is because his lord died, which is something that clearly would have been out of his control.
So because his life was thrown into disarray by something he couldn't control, he would feel that fate is cruel to people.