I just found the solution to this problem. As allways it was pretty obvious but the error was not
Previously i just flagged my entities for destruction and then iterated over them to destroy the bodies. This worked fine but the Problem was with the creation of the bodies (obviously doing that when the world was stepping).
The solution was, that i now add my entities to a list when they need to be created/destroyed. I create them before the step happens, and destroy them after the step finished.
It was kinda hard to find the solution, as it's only mentioned with 1 sentence at the end here: http://www.iforce2d.net/b2dtut/removing-bodies
"By the way, although this topic has focused on removing bodies since that is the most common case to cause problems, the creation of new bodies, and the creation and removal of fixtures must be dealt with in the same way."