Shaking one’s head left and right is understood as the sign for “no” in most human civilizations. There are a few exceptions where this is not the case (including some cultures in Southeastern Europe) but by and large, shaking one’s head means “no”.
If you spend time around babies, you might be able to intuit the answer.
Babies’ lives are pretty simple: almost everything they do revolves around eating, sleeping, and pooping. The second and third they can do at their own leisure, but eating requires communication to the caregiver about when to start and when to stop.
When the baby wants to refuse food, what does it do? The baby turns its head from side to side. It is this natural motion that has become near-universal for humans to show refusal or disagreement.
Image source: http://www.reflux.org.au/wp-content/uploads/2012/10/Feed-refusing-pic.jpg