Theseus' ship is less a paradox and more a matter of defining terms. And it applies only in the real world
For example - for a japanese, function and form defines the identity of something, not the atoms that made this something at one time.
For a greek, it's the atoms that make an ancient temple/etc.
About conscious beings (humans); indeed, for all living entities:
Did you know that the atoms that make you are completely replaced every ~7 years?
For the trekverse/ANY fictional universe:
The fictional persons/things/etc have no material existence. They are merely an amalgam of characteristics.
Meaning, the same characteristics that made Data/anything else will always make Data/said anything else.
No semantic hair-splitting about replacing planks that never exited in the first place.
About Janeway being resurrected by a god - irrelevant. It doesn't matter whether one's resurrected by technobabble, god, or the tooth fairy - or any imaginative combinations the comic lines came up.
It is STILL cheap, blatantly standard resurrection in its essence, meant to bring a popular (read - which sells comics/books) character back.
Because, while technobabble/magic allows for fictional resurrections, the real world does not. In the end, resurrections are only a facile wish-fulfillment fantasy, on the level of those marketed toward 7 year olds - regardless of the in-universe ...babble you came up with for 'explaining' it.
And because it cheapens the story - now everything is fair game for a reset button; who cares about what happens in a meta-story only interested in milking some popular characters for all they're worth, where everything can be reversed AKA nothing has any 'punch'.
If you truly care, Newspaper Taxi...well, it doesn't take much to get you invested in something, on the proverbial 'edge of the seat', does it now?