It feels to me like it is up to the author to choose what words will fit more properly. Does it become a paraphrase?
In what context?
In a context of, for example, a newspaper, the quote is translated, and remains a quote. For example, today Israeli newspapers were all translating the statement of the Kensington Palace regarding Kate Middleton giving birth to a third child. It remained a quote, even though at least one newspaper managed to mistranslate "Her Royal Highness" as "Her Majesty".
In a literary work, if for instance a character quotes Shakespeare, a translator would usually quote the best known translation of Shakespeare into the target language, and add a footnote/endnote/something regarding who's the translator of Shakespeare. This has the added advantage of the readers in the target language likely being familiar with the quote as presented, which fits the intention of the author in quoting Shakespeare in the first place. If no translation is available (for example if the literary work being translated quotes someone less famous than Shakespeare, or if a crucial detail is lost in the existing translations), the translator would then translate the quote himself.
In no case does the quote become a paraphrase. It remains a translated quote.