Since my last post I was able to re-locate where some of Bruce O.'s data had got to. He notes that Put in all appeared in Twenty four new Country Dances for the Year 1704, and also in The Compleat Country Dancing Master, as well as in DM.   I haven't yet checked the melodies to see if the one in Pills is the same melody as these dance tunes.   

The date of 1701 for Captain Kid's Farewel to the Seas may only be approximate. I haven't yet found a facsimile of the broadside. Some of the transcriptions state that it is undated. It seems to be nearly contemporary with Kidd's death, though, since it mainly restates facts that were established at Kidd's trial.   And it doesn't name him "Robert."

Another scholarly discussion of the ballad is William Hallam Bonner, "The Ballad of Captain Kidd", American Literature 15(4), 362-380, Jan. 1944.

Firth's Naval Ballads and Songs is available on Google Books here and here.