There is never a time where one MUST be used instead of the other that I can think of, but there are a few connotative differences between them.
"Befriend", to me, is more formal, and I would also be more likely to use it when talking about animals. (E.g. "I befriended a dog yesterday.")
"Make friends with" is the opposite: less formal, with me being more likely to use it when talking about a person.
Overall, however, the difference is slight - saying "I made friends with a dog yesterday." sounds perfectly natural as well. If there is a difference you should heed, it is the formality.