Playford Edition:

‘The Cushion Dance’ can be located in the 7^st edition of The [English] Dancing Master, (1686). 

Documentation Between 1603-1686:

 John Selden writes (1584-1654) about the 'Cushion Dance' in one of his minor works Table Talk, which was not published until 1689.  In it he states, "The court of England is much altered.  At a solemn dancing, first you have the grave measures, then the Corrantoes and the Galliards, and this is kept up with ceremony; at length to French-more, [it should be Trenchmore,] and the cushion-dance, and then all the company dance - lord and groom, lady and kitchen-maid, no distinction.  Son in our court, in Queen Elizabeth's time, gravity and state were kept up.  In King James's time things were pretty well.  But in King Charles's time there was nothing by French-more and the cusion-dance, omniumn gatherum, tolly polly, hoite come toite."⁽²⁾

Documentation Prior to 1603:

‘Cushion Dance’ is mentioned, in Thomas Heywood’s play A Woman Killed with Kindness, (written & performed in 1603/published in 1607). 

 Act 1; Scene 2; Line 34-35:

• “Nick: I, that have ere now deserved a cushion, call for ‘The Cushion Dance’.”⁽¹⁾