Magic can be used to coordinate but not to communicate.
Quantum entanglement lives in this middle ground. To resolve your paradox we must understand this middle ground.
Classical correlations: Suppose a machine splits a coin in half, separating the head and tail halves. It gives one half to Alice and the other to Bob, sealed tightly inside a box. Alice and Bob then separate. Once Alice opens her box, she immediately knows that Bob, who is lightyears away has the opposite face. However, each box already had it's face predetermined so nothing unusual happens. This is an example of local hidden variables. There is no causality.
Communication: After separation, Alice chooses whether she wants a heads or tails. Her box sends a radio signal to Bob's box which set's itself to the opposite of Alice's choice. This can only happen for causal time-like separations because of the radio signal.
Entanglement: Like the case of classical correlations, Alice can't choose whether she gets a heads (up) or a tails (down). No matter what she does she won't affect Bob. But unlike the classical choice, the entangled particles do what classical local hidden-variables (coins in boxes) can't, such as violating Bells inequality and playing coordination games.
Non-locality means that if we were to model the quantum state on the computer we would need to have Alice and and Bob modify and/or measure the same shared state no matter how far they are apart. However, they are restricted in what they can do to/with this joint state so they can't use it as a channel to send information. In addition, it does not matter who goes first, so no matter what frame we choose (which affects who is first if they are spacelike-separated), Alice and Bob's results will be the same. There is no paradox.