You don't really understand the ship of Theseus if you think that. Replacing with different things not just identical pieces is part of the question.
> The ship wherein Theseus and the youth of Athens returned from Crete had thirty oars, and was preserved by the Athenians down even to the time of Demetrius Phalereus, for they took away the old planks as they decayed, putting in new and stronger timber in their places
( https://en.wikipedia.org/wiki/Ship_of_Theseus , but this isn't exactly obscure material. )
The entire project is to replace a failing part of the ship with an identical, but not yet failing, part.
I'm surprised also by your take on the paradox. I've always understood that the difficulty lay with the use of identical materials to replace the old ones.
It might be clearer to consider the similar formulation of 'Trigger's Broom' from the show Only Fools and Horses on UK tv. Trigger has the 'same' broom for years, despite having replaced the head several times, and the handle several times. Clearly the same materials are used here.
I would say that replacing the wooden planks with metals ones is less of a paradox - that is more clearly a different ship! Replacing the decayed planks with other decayed planks makes no sense, so I don't understand your perspective on this ...