If you look at the implementation of btCollisionWorld::removeCollisionObject() you can see what it is doing. My guess would be the cost of removing from the broadphase is the most expensive part. If I wanted to remove ALL objects at once then I would derive MyDynamicsWorld from btDiscreteDynamicsWorld and give it a clearAllCollisionObjects() method that does the following:
(a) delete the broadphase and then add a new empty one (b) clear the m_collisionObjects array, and (c) clear m_nonStaticRigidBodies.
Note: that would leave dangling "worldArrayIndices" on the btCollisionObjects so if I was going to recycle those I would need to go through and clear those indices, else delete 'em.