^ +1 on pretinning, if you are using a hot air gun. Paste has a lot of drawbacks with the advantage of being able to set parts down for oven reflow. Or if you are proficient at using a solder paste dispenser, it can be quite fast, apparently.
One difference, I set the chip on top of the pretinned pads before reflowing it. Flowing it first seems like you are just burning off your flux? I dunno. If it works, it works. Pre-tinning works.
The paste is going to reflow into liquid solder, same as the pretinned solid solder. Solid solder stays on the pads, even if you have to reposition the chip many times when placing it. Paste doesn't. Applying paste the way you have pictured, some may solidify into balls in the space between pins or even bridge, even if you place the chip, perfectly. The only caveat with pretinning is you have to reflow all the pads at the same time with this method, so for larger IC's this might be a challenge.
There are also different grades of solder paste. If you can see the solder balls without magnification, you are probably using coarser paste. Did you buy it in a jar? The stuff sold in a syringe is usually finer and easier to use by hand.
•Would a stencil from the board-house significantly speed up the process?
Maybe for you. Stencil pasting is an art. It's definitely not a color-by-numbers thing where it works every time, all the time, and parts magically realign themselves no matter what. I have dealt with professional board assemblers that won't even do no-lead parts. I have tried to use framed stainless steel stencils on two projects, and my own results are poor on the fine pitch ICs. No time or effort was saved. The conundrum is that the smaller the panel, the easier it is to paste, cleanly, but the more time you spend pasting. Trying to paste a large panel can be very challenging. So the more time you spend cleaning off boards and repasting.