In this paying case, sometimes we omit the preposition, but that is not very good. When some verb asks for a preposition, we must use it.
Since the men are receivers of the payment, we use "a" or "para".
Other verbs like "dar", for instance, would never allow the preposition to be removed:
"Dar o dinheiro aos homens" = to give (to) the men the money
I believe that would be "Ele finalmente paga pelos homens" (pelos = por+os). I have found that knowing when to use "por" or "para" as the translation of "for" is rather tricky. This should help: http://www.learn-portuguese-with-rafa.com/por-and-para-in-portuguese.html Note that "por" = "on behalf of".