In general I think the predictor should mimic the physics engine as much as possible. For velocity & position, your Predict seems to be doing a variant of Størmer-Verlet, while (if you're on Unity) PhysX apparently does semi-implicit Euler, which my physics engine also uses, so that's what I use in my prediction code:
- forceAtPosition, acceleration as before
- currentVelocity += acceleration * deltaTime
- nextPosition = currentPosition + currentVelocity * deltaTime
- (assign nextPosition to positions[i], currentPosition)
Also make deltaTime the same as what PhysX uses. Oh and if your planets move, make sure to use their future (not current) position for the force (and if your planets also move under gravity... you need to predict everyone at the same time :) ).
