It looks as though no one ever answered jbeanmusic's question. Is there any record of the ballad being sung to the shape-note melody?

I would offer three points:

(1) The name of the shape-note melody. A plausible reason for naming a hymn tune Captain Kidd is that it was already known by that name.    A plausible reason for it being known by that name is because it was sung with the ballad.

(2) If you are willing to accept it, there is the evidence of one of Harriet Beecher Stowe's semi-fictionalized memoirs of her childhood, Oldtown Fireside Tales. This work describes "Sam Lawson" singing the ballad (and commenting on it as he goes). Stowe writes:

A most wailing minor-keyed tune was doled forth, which seemed quite refreshing to Sam's pathetic vein, as he sing in his most ligubrious tones, -

My name was Rober Kidd
As I sailed, as I sailed,
My name was Rober Kidd;
GOd's laws I did forbid,
And so wickedly I did,
As I sailed, as I sailed

I would not call the shape-note tune "wailing" or "lugubrious," but perhaps a mid-Victorian might.

(3) Ethel and Chauncey O. Moore, the authors of Ballads and Folk songs of the Southwest (Norman, Oklahoma, 1964) collected a version of "Captain Kidd" from a Tulsa informant, who claimed to have learned it "while on a Boy Scout Jamboree". "Captain Kidd" was not published in Ballads and Folk songs of the Southwest (not in the edition I saw, at any rate.)   The Moores planned a second, larger, work, The Ballads and Songs of Oklahoma. As far as I know, this was never published, but the manuscript is in the Western History Collection of the University of Oklahoma Library, where I was able to see it. The tune they collected from their informant is, to my ears, clearly related to, and possibly derived from, the shape-note tune.