It is precisely because "leave no stone unturned" and "explore every avenue" are honored by centuries of use that Orwell didn't like them. He states very clearly in this essay that:
modern writing at its worst does not consist in picking out words for
the sake of their meaning and inventing images in order to make the
meaning clearer. It consists in gumming together long strips of words
which have already been set in order by someone else, and making the
results presentable by sheer humbug. The attraction of this way of
writing is that it is easy. It is easier — even quicker, once you have
the habit — to say In my opinion it is not an unjustifiable assumption
that than to say I think. If you use ready-made phrases, you not only
don't have to hunt about for the words; you also don't have to bother
with the rhythms of your sentences since these phrases are generally
so arranged as to be more or less euphonious. When you are composing
in a hurry — when you are dictating to a stenographer, for instance,
or making a public speech — it is natural to fall into a pretentious,
Orwell makes the point that "language can corrupt thought." Writing that relies on cliches and what Orwell calls "flyblown metaphors" tends to become automatic, creating a pattern of thought that likewise becomes automatic, oversimplified, less than incisive. Writing in cliches makes writing more accessible because people like familiarity, but Orwell was forever searching to shake up the status quo, to challenge weak writing that refuses to think for itself, but instead relies on hoary constructions that virtually all writers fall back on to avoid the hard work of originality. His first rule for writers who wish to persuade, which answers the question posed here:
Never use a metaphor, simile, or other figure of speech which you are
used to seeing in print.
Other advice that he includes in this essay:
Never use a long word where a short one will do.
If it is possible to cut a word out, always cut it out.
Never use the passive where you can use the active.
Never use a foreign phrase, a scientific word, or a jargon word if you
can think of an everyday English equivalent.
Break any of these rules sooner than say anything outright barbarous.
Orwell, by the way, recognized that he was often guilty of violating these principles himself.