This is my tentative response:
Let X = the content of an earlier utterance.
It seems to me that a "restatement" expresses X again, in the same or different terms, usually for the purpose of rhetorical effect (e.g. emphasis).
A "paraphrase", on the other hand, expresses X again, in different terms, usually for the purpose of clarification.
I would therefore call "paraphrase" a subset of "restatement".
1. We are both perfectly well aware, you and I, that the simplest questions result in the longest threads, on ESL forums.
Here, "you and I" restates "We", for rhetorical effect.
2. We are both perfectly well aware that the simplest questions lead to the knottiest threads, on ESL forums; and by "knottiest threads", I mean threads where native speakers entangle themselves hopelessly in all kinds of complex, pointless speculation, for no apparent reason.
Here, the underlined part is a paraphrase of "knottiest threads".
But as I say, it's only a tentative reply; someone else may have a better explanation!
All the best,
Student or Learner