Your arguments are strong, however have you considered an algorithm based on the laziness and cheapness of humans? Consider that a lot of propaganda is heavily coordinated and not creative in the sense of being centrally created and issued.
An algorithm could watch, say, 50 sources and see if they simultaneously start using identical phrases, given access to a thesaurus aren't those odds a little unusual? This happened a couple times in the last election. You'd have a much simpler task of quote analysis of course, to exclude directly quoted content.
Then factor in something to detect press releases and video news releases where the verbiage of large sections is identical, this strategy is almost too easy.
Another factor is "large known propaganda sources" simultaneously releasing the story but small propaganda sources don't operate at all because fundamentally there is a size cutoff. The Wash Post will be in every propaganda operation because they are huge, but the "nowheresville register" certainly will not. Real news would of course be covered by both, so it should be very easy to detect organic self organizing behavior vs small scale conspiratorial behavior.
Now algo-proof propaganda could emerge much like handwritten letters to your congressional representative, before being inevitably ignored, are considered more impressive than mere form letters or signing a list. But it would detect at least some fake news based on fake news being part of a coordinated centralized mass produced campaign rather than trying to detect fake news based on its inherent fake-ness itself. Sorta like swatting bugs that bite you or try to, rather than identifying each individual bug then swatting only the mosquitos. Its very difficult to detect if something is a Walmart product, but its easy to detect if its mass produced, if the quality is very low, if it was made in China, if it contains chemicals banned in the USA for safety reasons, and in the long run works just as well.