I don't understand why this is considered a paradox.

It is only a paradox due to flawed thinking of what is considered the same. The problem is when you think of same object as a binary (it is same or it isn't). If you think of same object as a spectrum it becomes trivial.

In case of the mentioned ship, as individual pieces are replaced, what's same becomes smaller and smaller part of the entire ship. If you take these parts and build another ship, that will be the same ship that you originally had.

Thing is, considering an object as a spectrum leads to other problems. If continuous spectrum, then _any_ adjustment gives you a new object: e.g., a wave eroded a few atoms from the hull, now it's a new ship. If discrete spectrum, then same problem as before.

You're still thinking in binary there. If a wave eroded a few atoms from the hull it's now the tiniest bit a new ship. If you round it to the nearest binary result you'd end up with "It's not a new ship".