I suggest to use EPSG:25832 ETRS89 / UTM zone 32N, because the Gauss-Krueger DHDN CRS zones are based on the old bessel ellipsoid, and you have to apply a datum shift that is not constant over the whole of Germany.
ETRS89 has no datum shift to EPSG:4326 WGS84 which you can get from GPS receivers, and all official cadastral information has beeen moved to ETRS89 by now.
You could set up a local transverse mercator projection on a center point of your area of interest as well, but that would gain only little improvement on accuracy against UTM.
By the way, EPSG:3857 has no real meters as units, they match only at the equator.
It sounds like there may be a misunderstanding of the difference between defining a dataset's projection and reprojecting the data itself. This ESRI blog post does a pretty good job of explaining the difference, and this QGIS documentation explains the underlying concepts.
In short, every dataset has a CRS—a way of defining what it's coordinates mean. Some are lat/long, others are easting/northing from a specified origin (like UTM), and there may be other more esoteric CRS's out there.
Defining a dataset's projection tells dataset to say it's using a specific CRS, but doesn't actually change the coordinates of the data. It's entirely possible (and common) to define a CRS that doesn't match the actual coordinates. This usually results in data in weird places, funky scales, etc. Like Michael said, don't redefine the projection unless you are certain it's wrong.
Reprojecting a dataset involves mathematically changing the coordinates of the data (and automatically defining the projection at the same time). I often reproject data from a UTM-based projection to a US State Plane-based projection when I'm pulling in data to my database.
When you set a project CRS, you are telling the software which projection to use to display the data on the 2D surface of the monitor or the paper. Different projections have different tradeoffs and are suited for different uses. The on-the-fly transformation automatically translates the dataset's CRS to the project's CRS for display only (it doesn't change the data itself), allowing you to add data that doesn't match the project CRS without first reprojecting the data.
Based on what you said about changing the CRS of all the layers, I suspect you redefined the layers' projections without actually reprojecting the data. Then, when the on-the-fly transformation chose where to place the data on the map, it put it in the wrong place because it was interpreting the coordinates incorrectly.
Best Answer
To add to Andy W's comment/answer:
You could (should) generate a test dataset with cross-checking via multiple different 3rd-party re-projection APIs, giving you more confidence that you're not just reproducing, for example, a proj.4 bug.
Also, you can create various identities, modulo floating point error, that you can test in a randomized way -- e.g. round-tripping through CRS A -> CRS B -> CRS A should give you the same point you started with.