Often the poet proclaims that God is in control, "Fate goes as ever fate must." Yet the characters are constantly told that their choices are their own. How does one justify these seemingly paradoxical statements?
In terms of religion, free will is offered along with encouragement to following the precepts of Christianity. Fate is what awaits one, based upon the choices that he or she makes. We have a part in our fate by making choices, but in following Christian doctrine, the sense is that God has a hand in our fate as we make choices with His will in mind. Personally, I feel that while God loves us unconditionally and wants what is best for us, he allows that we have the choice to follow the teachings of His Son or not. He never stops loving us, but our fate is left in our hands. Using his Word to guide us allows us to choose the path we take, leading us to the fate that God knows (being omniscient) we will come to, but giving us the option of doing what we want to do. Giving us no choice seems to negate the very idea of free will; this is how I see the two concepts.
Some Christian traditions would find no paradox at all in the mingling of fate with freewill. For some, we have the freewill to choose whether to be saved or to be damned, but God directs our every move, that everything that happens to us for good or for bad is God's will. In a sense, fate has been replaced by "God's will."
I would be tempted to read it as that the men themselves have freewill and choice but that they cannot influence or have any effect on Grendel. In the poem, Grendel is seen to be one of the fallen, a descendant of Cain and therefore already doomed. (Check out the discussion on this in the post about having sympathy or not for Grendel). So if Grendel is already doomed and acting in accordance to the laws of evil, then the men themselves have no way of influencing whether or not Grendel gets them or attacks again.