a) If you travel close to the speed of light, causality goes more slowly (e.g. a clock ticks more slowly) than it does for someone who is stationary. So, two clocks will diverge. This is true, AFAIK.
b) If you travel close to the speed of light, and somebody else is stationary, they are traveling "into the future" relative to you, whereas you are "in the past" relative to them. I believe this is nonsense. But, I believe this is required for the "Andromeda Paradox" to hold. Thus, I don't think it holds. (BTW, we know that paradoxes never hold, so there must be something wrong with it.)
The solution to the Andromeda Paradox that I am proposing is to say that there is one universal ordering of events (among both observers and the Andromedans), but the two Earthling observers have different times on their clocks at the particular point in the sequence of events where the Andromedans decide to invade.