When you pull the plugs (one per cylinder is fine) you are looking for metal crammed into the electrode (you can figure out what that means) or oil buildup on the plugs (again, it ain't a good sign).

I doubt the starter locked up and caused the blue smoke while the car was going, however, it could be possible that the teeth are ground off the flywheel/starter, and that is why the starter spins with no engine turnover. But, even if you set the whole damn starter on fire, you would not get a plume of thick blue smoke out the back, and certianly not out of the tailpipe. But, bad teeth on a flywheel/starter gear do make the noise you describe. However, the fuel smell is still puzzling.

If you just replaced that cats (or cat) the problem may be serious engine meltdown on that side, caused by some sort of improper sensor reading in the Cat making the engine go very lean, and causing a meltdown (i.e., the O2 sensor told the engine the mixture was too rich when it ws not). If you do pull plugs, and the color is super light (or you see chunks of metal in there) that is what happened.

Let's hope it is just starter/flywheel related.