He was given the exact opposite order, so was von Manstain. After all it was a matter of going to a military court for disobeyance, losing all the prestige and gain public humiliation plus certain death.
Besides, Paulus was promoted to a feldmarshall, and prior to him no officer in that position ever surrendered - clear sign that he should fight to the last man, don't you think.
Why the Germans lost? Well the Red Army has quite a large rear, and even larger human resource. The counter offensive on the 19th of November was briliantly organized and Paulus was fast to lose the support of the hungarian and romanian divisions. That along with the specific orders of the furher to never surrender nor step back made the loss possible. After all von Manstein couldn't crash the blockade of the city, and Paulus knew what will wait for him if tried to leave the city and join the South Army. I'm not stunned even by the fact that Paulus joined the Red Army to support the Soviet propaganda.