According to The Wordsworth Dictionary of Proverbs (1993), a proverb involving the turning of a worm dates back to at least the middle of the sixteenth century—considerably earlier than the publication date of Shakespeare's Henry VI, Part 3, which Wikipedia dates to 1591. Here is the Wordsworth Dictionary's entry:
Tread on a worm and it will turn. 1546: Heywood, Proverbs, pt. II. ch. iv. , Tread a woorme on the tayle, and it must turne agayne. 1592: Greene, in Works, xii. 143 (Grosart). 1638: Ford, Fancies, V.i., I am, my lord, a worm ; pray, my lord, tread on me, I will not turn again. 1710: S. Palmer. Moral Essays on Proverbs, 305. c. 1800: J. Trusler, Proverbs in Verse, 195. 1816: Scott, Old Mortality, ch. xxvii. 1922: Weyman, Ovington's Bank, ch. ix., The worm will turn, and Thomas ... did turn.
The wording in The Proverbs of John Heywood (1546) is indeed
Tread a woorme on the tayle, and it must turne agayne.
The 1874 edition of that book notes that the quotation from Henry VI, Part 3 runs as follows:
The smallest worm will turn, being trodden on ;
And doves will peck in safe-guard of their brood.
The instance from John Ford, The Fancies (1638) is likewise as reported by Wordsworth.
In any case, the notion that a worm will turn when it is stepped on was already a proverb in 1546, and may well go back considerably farther.