Orcs were not created by Sauron. They first appeared in the First Age, the work of the first Dark Lord, Morgoth, who Sauron served at the time. That said, Morgoth did not 'create' them either. Only Eru (Middle-Earth equivalent of God) was capable of creating life. Morgoth twisted other life of some sort into Orcs, though Tolkien spent his whole life wrestling over their exact origin.
The men of the east and south were loyal to Morgoth/Sauron, because they had known little else. His enemies in the west were the descendants of those who wanted to escape the Morgoth in the First Age and then met and fought alongside the Elves who were also fighting Sauron. There was very little opposition to him in other lands.