As I implicitly stated, there's only two (significant) calculations when you add something - creating objects, and inserting in broadphase. You need to determine which is causing you problem, exactly as bateleur says.
If it's the broadphase, none of these tricks will work, it's just as expensive to move something a long distance in the broadphase as it is add it. In that case you could try
QueryShape (which may require some reverse porting). It has none of the start up costs, but it's slower if you are going to be calling it every frame.
If it's object creation, then do pooling, then worry about the other details. This makes a decent difference, so I've been slowing cutting down on allocations inside Box2DFlash.
There's a lot of calculations that go on in bringing a new shape into the world. It means that a shape that suddenly pops into existence collides and squeezes stuff out of the way.
I don't consider position correction to be part of creating a shape, it's part of the general engine. But if you are creating lots of shapes near on top of each other, it is going to hammer the engine. If this is your bottle neck, you are pretty much stuck. Turn down the engine accuracy, or give it less work to do.