Doesn't this mean "Everyone has not eaten today"? --i.e., Nobody has eaten?
not exactly, it means that "not all of them" have eaten, i.e. a number of them did eat, but others not.
And to say "Nobody has eaten." it would be "Personne n'a mangé."?
Could you also use "Pas tout le monde a mangé aujourd'hui."? Is there an easy rule when you can use pas at the beginning?
You can use it, but it is not very elegant, and you should add the other part of the negation:
"Pas tout le monde N'a mangé aujourd'hui".
"Tous n'ont pas mangé aujourd'hui." What's wrong with that?