That's not a paradox if you distinguish between a lie and a false statement. If Pinnochio does not expect his nose to grow, then he is lying, and his nose will grow; he has lied but in so doing made a coincidentally true statement. If he does expect his nose to grow, then he is telling the truth as far as he is able, and it will not grow, even though he would be mistaken in the statement.
If Pinnochio's nose detected absolute truth, then there really should have been a subplot in the story about people who want to kidnap him and pose him questions to determine the ultimate nature of the universe.
The Epimenides Paradox or Liar Paradox is "This sentence is false." Type hierarchies are supposed to resolve the Epimenides paradox... Using an indefinitely extensible, indescribably infinite, ordinal hierarchy of meta-languages. No meta-language can contain its own truth predicate - no meta-language can talk about the "truth" or "falsity" of its own sentences - and so for every meta-language we need a meta-meta-language.
I didn't create this video and I don't know who did - but it does a pretty good job of depicting how I feel about infinite type hierarchies: namely, pretty much the same way I feel about the original Epimenides Paradox.
Bonus problem: In what language did I write the description of this video?