I would like to have asked Bruce O. about the broadsides he had knowledge of. None of the five Captain Kidd broadsides I have access to is dated, or specifies a tune. Most have no place of printing, either, but one has this note: "Sold at the Bible and Heart in Cornhill, Boston". I think this suggests the later 18th century. This is consistent with the use of the name "Robert Kidd". Contemporary accounts of Captain Kidd's trial and execution all know that his first name was William, not Robert. Presumably some time passed before the ballad began to circulate.

All five of the broadsides begin

You captains brave and bold hear our cries, hear our cries,
You captains brave and bold, hear our cries.
You captains brave and bold, though you seem uncontroul'd,
Don't for the sake of gold, lose your souls, lose your souls,
Don't for the sake of gold, lose your souls.

This lays down the full stanza pattern. Subsequent stanzas leave the repeats at the end to be understood from this pattern, and so don't print them explicitly.

The earliest melody in this meter I have found is the tune for "A young man and a maid", a.k.a. "Put in all", which was in p. 251 of the 6th volume of Wit and Mirth; or, Pills to Purge Melancholy (1719). (Bruce O. didn't mention a specific date in his post above.)