Who first solved the two-body problem in 3-dimensions? Was it Laplace?
(1) Newton's consideration of the two-body problem includes right from the start his statement and proof of the planar character of the motion in space, in his first two propositions of the Principia, which contain no intrinsic or a-priori restriction to two dimensions:
Prop.1 : "The areas, which revolving bodies describe by radii drawn to an immovable centre of force, do lie in the same immovable planes, and are proportional to the times in which they are described."
Prop.2 : "Every body, that moves in any curve line described in a plane, and by a radius, drawn to a point either immoveable, or moving forward with an uniform rectilinear motion, describes about that point areas proportional to the times, is urged by a centripetal force directed to that point."
(These statements can be seen at pages 57 and 60 in the contemporary (1729) English translation of Newton's Latin (based on the Principia's 3rd edition, of 1726), available online at https://books.google.com/books?id=Tm0FAAAAQAAJ . Each statement is followed by its associated proof, and Conifold's comment has already effectively given the gist of the proof of planarity found in Proposition 1.)
(2) The enlargement of the question in a comment ("Does [Newton] just assume central forces?") appears to presuppose that Newton gave his mathematical demonstrations and physical inferences by running them together.
This presupposition is not justified: Newton's writing for the most part shows particular care to separate mathematical reasoning from physical inferences. He also emphasised in effect the different (lesser) degree of certainty associated with physical inferences as compared with mathematical demonstration (see e.g. Principia Book 3, 'Rules of Reasoning in Philosophy', esp. Rule IV ).
An example of the separation is seen in Book 1 Proposition 4 and its corollaries (with mathematical demonstrations about some consequences of different conceivable laws of centripetal force, including the inverse-square among others) and its scholium (with comments of a more tentative character about how observations by named observers match an inverse-square law).
Thus, in Proposition 1, what Newton shows is theoretical and mathematical, i.e. that if the force on an orbiting body is directed to a centre which is either at rest or moving uniformly in a straight line then (among other things) the motion of the orbiting body relative to that centre is confined to a plane. The question whether such a situation exists, exactly or approximately, in the real world, is treated elsewhere as a separate matter.
Newton's identifications and demonstrations of several different features of two-body motion are spread over a number of different propositions and corollaries in the Principia, and questions of how closely the actually-observed motions of celestial bodies might match this essentially mathematical model are treated separately again.