How should cooked pork shoulder be stored in the freezer?
I don't see a strong reason to wait for the meat to cool completely before vacuum sealing it.  In fact, by waiting, you're likely to let more flavor and moisture escape unless you've already put it in a well-sealed container.

The only reason to wait would be if you were vacuum sealing very large packages, which might take very long to cool down in the center.  But if your packages are a reasonably small size and/or flat enough to cool quickly, it's probably fine to seal early.

I would strongly recommend cooling and chilling before freezing, however.  Please do NOT cool outside of a refrigerator unless you are using an ice bath or something like a cooler as recommended by Sean Hart.  (That is, do NOT just cool on the counter.)  If you can't do that, the refrigerator is fine for cooling thin or flat packages -- just don't put hot food in touch with perishable food inside the fridge, and don't stack packages (you want to maximize air circulation).

It's important to chill before freezing because the rate of freezing is important for preserving the best quality in meat.  If it takes a long time for meat to freeze, larger ice crystals will form during the process, which create a number of problems (more chance for "freezer burn," meat loses more juice and tastes drier when reheated, etc.).  So chill the meat well, and then place in freezer.  Again, try not to stack packages or place them too close together when freezing, since you want them to freeze as quickly as possible.  (Depending on the size of the freezer and how much meat you're freezing, it may also make sense to freeze in batches, since adding too much food at once to a freezer may make it less efficient and less able to freeze quickly.)

As for the last question of whether or not to sauce, I think that's more of a personal preference question.  I could see potential advantages if you remove air more efficiently if you add a little sauce, not only for the sealing process, but in the freezer where having more leftover air in a package tends to encourage "freezer burn" and can create quality issues.  But it really depends on whether the vacuum sealing can work efficiently even without the sauce.