I would give a fair hearing to anyone's rendition using the "Fair Flower of Northumberland" tune. However, I agree with Malcolm not to be hasty. Another tune might work better.

The problem is that "The primrose of the wood wants a name" is in a different meter than the other refrain line, "you are the fair maiden of Coldingham," so I doubt a tune will easily be found to accommodate the song as is. Another option would be to compose a tune, but the result would still sound asymmetrical.