"We have not paid for the chicken."
Translation:Wij hebben de kip niet betaald.
You're right, it could mean that. But it can also mean we haven't paid for the chicken. And since people don't give money to animals very often, it usually means paid for the chicken. Usually this sentence means paid to when dealing with people (I'm ignoring human trafficking for now), and paid for for animals or things, like in the given sentence.
I'm not sure why it can be left out, but if you change the word order to: Wij hebben niet betaald voor de kip. it cannot be left out. And then paid to the chicken is Wij hebben niet betaald aan de kip.
"Niet" is in reference to verbs and "geen" is in reference to nouns.
Ik kan niet zingen. (I can't sing.) Hij heeft geen bier. (He doesn't have any beer. -or- He has no beer.)
In the case of "geen", it helps me to think of how it could be said in English. For instance, could "They don't have any money" also be "They have no money"? In this case, yes, so it would be "Ze hebben geen geld."