In reality they are both moving with their own relative velocities
Sorry, but that statement is so bad that it is not even wrong. In space, there is no such thing as an absolute speed. When you have two objects, you can only ever measure the relative speed of those. Asking how that relative velocity is distributed among the two objects - whether one is stationary or whether both are moving - doesn't even make any sense, unless you include a third object. There are reasons to include a third object, one of them if the reference frames of the objects significantly accelerated, but I don't think any of those apply here.
It's kind of like being in aircraft 1 (speed 500 mph) and measuring aircraft 2's speed (also 500 mph) and concluding aircraft 2 is actually going well over Mach 1 because they are flying in opposite directions and you aren't accounting for aircraft 1's own velocity.
Those speeds are not the "real" speed of the aircraft either. 500 mph refers to the speed compared to the air, the aircraft are moving in. Which is very relevant, because that determines how the aircraft handles, how much fuel is used and so on. But the air is moving at the equator with roughly 1000 mph compared to the center of gravity of the earth. So if one aircraft was moving east and the other west at the equator, one would have a speed of 500 mph and the other one of 1500 mph when compared to that. And even that is not the end of it, because the center of gravity of the earth moves around the sun and then the sun moves around the center of the Milky Way, which moves relative to other galaxy. So for the aircraft, there is no such thing as a correct speed and what you want to know depends on the question you are asking. If you want to know whether the aircraft is supersonic or not, you need to measure the speed relative to the air around. If you want to know how long it takes until two planes 1 km apart collide, you might as well assume that one aircraft is stationary and the other one is moving at 1000 mph. That is as good as calculating their relative speed to Andromeda (assuming we can neglect time dilation), but much easier to calculate.
In space, there is not enough air to be consequential, so that frame of reference won't be useful at all.
Yeah but a frame of reference centered on the sun isn't super useful for these sorts of calculations precisely because the sun really isn't stationary. I mean nothing is, but assuming it is gives you velocity estimates for other objects that are not close enough to reality to be useful for anything but back of the napkin estimates.
[...]
I truthfully don't know what a good reference frame would be for this situation, just that a sun-centered one that is assumed at rest is not a great one but will get you in the correct order of magnitude.
The sun is one of the best reference frames you can use for this, because what else are you going to take. The center for he Milky Way comes to mind, because the sun is in an accelerated motion around it, but for this problem it is a rather bad one. Apart from that we don't know exactly where it is, the effect is pretty small over 70000 years. If you assume that the sun moves in a straight line relative to the center instead of the real, curved orbit, you make an error of roughly 5E-5 light years (about 3 AU). Since the other star feels roughly the same acceleration towards the center, the relative effect will be even much smaller. I don't think that we know the distance right now to a precision of 10^-5, much less the distance 70000 years ago. So it doesn't even make sense to include the effects of the motion relative to the center of gravity into account when you want to know the relative motion.
In fact, I would assume that since the distance between the sun and that star was supposed to be quite small in the past, the effect of assuming constant motion instead of accelerated motion caused by the attraction to each other is much bigger than anything else. Even if you needed a really accurate number, you would probably mostly look at effects that the gravitation caused the nearest stars has. So you would be looking at a multi-body problem, in which none of the bodies is really dominant. So choosing the sun as the reference point is really the best option here, because there is no reason to choose anything else over it and at least you know quite accurately where it is, relative to you. Any small acceleration of the sun can then be handled by a small pseudoforce acting on all other objects.
Long story short: Assuming that the sun is stationary isn't just good for a calculation on the back of an envelope for this problem, but it is really what you should do!