I seem to intuitively think of machines as "bottom-up" constructs consisting only of smaller parts, whereas I view creatures as "top-down," that is to say that I consider the whole as the only significant part. I have a lot of preconceptions on this matter. Maybe it's because I know that all machines are deliberately constructed, whereas biological organisms develop organically.
To me, the ship of Theseus is a machine, which renders Theseus' paradox moot and purely semantical in the canonical thought experiment. But when Theseus' paradox is applied in the context of, say, brain cell replacement, I find it much more challenging and risky (and I'm afraid of the potential loss of life).