What happens when a player pays more than what they owe for rent?
Yes, you must give them the correct change.

This is not an issue of a specific rule, but rather just one of how "paying things" in general works, both in games and real life. If you owe someone $16, a valid way to pay that $16 is to give them $100 and ask for $84 back. If the person doesn't have $84 to give you in change; then the two of you work out how to get that change from the bank... there's no difference between you making change and giving the other person exactly $16, or the other person making change with your $100 and returning $84 to you.

In case a rules quote does help:


  PAYING RENT… When you land on property owned by another
  player, the owner collects rent from you in accordance with the list
  printed on its Title Deed card.


The key being that they can only collect the amount printed on the Title Deed card. They aren't allowed to collect any extra.