What is the origin of the phrase "burden of shame"?

"of shame" is merely and adjectival modifier.

OED:

Burden:

2. figurative.

a. A load of labour, duty, responsibility, blame, sin, sorrow, etc.

Its use of "burden of + abstract noun" in this sense dates back over a thousand years to

α. c971 Blickl. Hom. 75 Swa sæt þonne seo unaræfnedlice byrþen synna on eallum þysum menniscan cynne. [Thus sat their so intolerable burden of sin as a whole storm of human sin]

Burden of shame is no different from burden of blame, sin, sorrow, etc.

The Scarlet Letter: A Romance - Volume 1 - books.google.co.uk › books, Nathaniel Hawthorne · 1852 Found inside – Page 189

The stigma gone, Hester heaved a long, deep sigh, in which the burden of shame and anguish departed from her spirit.

The earliest match that a Google Books search finds for "burden of shame" is from a sermon on Zechariah, chapter 3, verses 9 and 10, in Peter Hewat, Three Excellent Points of Christian Doctrine (1621):

There is no burden nor weight comparable to the burden of sin that hangeth so fast on, and presseth down. The burden of sicknes, of long and heavie sicknes, is a heauie burden. The burden of shame and ignominie, a heavy burden, which maketh David so earnestly cry to God in his 119 Psalme, to deliuer him from that shame which he feared, aad his sin had deserued. The burden of disdaine and contempt, a heavy burden. We are counted, saith the Apostle, the off-scowrings of the World. The burden of povertie and want a heavy burden. ... But of all these burdens none of them can compare with the burden of sinne, lying vpon a mans conscience vnpardoned.

The Early English Books Online database finds three other instances of the expression from the seventeenth century. From A True Relation of the Queens Majesties Return out of Holland and, of Gods Merciful Preservation of Her from Those Great Dangers, Wherein Her Royall Person Was Engaged Both by Sea and Land (1643):

These Ships, (upon Advertisement brought them of the Queenes comming) were seen to hye away presently from Newcastle, where till then, they lay to doe such Service as they were directed to. And where, they are said, to have bragged, they would board, sinke, or sinke with the Queenes Ship, could they meet it. Gods Goodnesse gave them not the power of tryall by Sea, though the Divells malice in them, made them attempt to doe that Mischief by Land. And to doe it the better, in the Night they landed some of their Men on shoare, who were heard to enquire for the Queenes Lodging at three of the Clock, which they shot at by six, a shroud suspition (with the rest) what was the Mark they aimed at.

Whether by Commission, and by whose, these bould Men did this barbarous Outrage, the Justice of Heaven and Earth will doubtlesse concurr to examine and punish, that so great a Blot, and Burden of shame and Guilt, may not lye on the Nation.

From William Greenhill, An Exposition Continued upon the Sixt, Seventh, Eighth, Ninth, Tenth, Eleventh, Twelfth, and Thirteenth Chapters of the Prophet Ezekiel, with Useful Observations Thereupon (1649):

The Lord hath burdens for Princes: if they be wicked, there be burdensome Prophecies against them, and burdensome judgements for them, Zedekiah did evill in the sight of the Lord, 2 K. 24.19. And you may see what burdens he had.

1. A burden of fear, he durst stay no longer, and Jer. 38.19. I am afraid of the Jewes fallen unto the Chaldaeans least they deliver me into their hand.

2. A burden of shame, he covers his face, he will see none, nor be seen of any; he leaves Jerusalem in a shamefull manner, carrying some burden upon his shoulder, as if he were some vulgar man, he is disguised as being asham'd of a Princely title.

3. A burden of flight, he is put to it, to flie for his life.

4. A burden of darknesse, in the evening or night he steales away.

5. A burden of difficulties, he must dig through a wall, goe in by-wayes.

6. A burden of sad judgements.

And from Jeremiah Burroughs, Christ Inviting Sinners to Come to Him for Rest (1659):

Secondly, The remaining part of corruption in the hearts of the saints, it is a burden of shame, greif is a burden, and shame is a burden, many that can beare great burdens, that can beare the burden of poverty yet are not able to beare the burden of disgrace, especially to those that are most ingenious, it is one of the greatest burdens in the world, now the saints they are ashamed of the corruption that remains in them, they account it a shame before the Lord and before his blessed Angels, and in regard of themselves, what they know of themselves that the world knowes not of, they look upon it as ashame that they do even loath and abhor themselves as the scripture speakes; it may be their lives are such as others do honor and have high thoughts of them, but they being acquainted with their own hearts, and looking into the secret working of their own spirits, they see so much evil there, as they see much cause to abhor and loath them∣selves, and to lie down in their shame before the Lord, whom they know doth see into their hearts a great deale more then they can see themselves. I wil appeal to any one that knows his owne heart, if God should open your heart and make it known to your friends and acquaintance so much evil as is in your heart in the performing of one duty, if al men should know so much evil as is in your heart at one time, in praier or hearing a sermon, would you not be ashamed, now God knowes and sees al the baseness and vildness of your spirits, and the godly knowing this, they cannot but be ashamed and go under this burden of shame with heavy hearts.

These instances treat "burden of shame" as a sense of guilt arising (variously) from ignominious actions publicly discovered or from perfidy (against the Queen) or from conduct unbecoming one's office or from consciousness of spiritual corruption. That probably covers the waterfront as far as traditional use of "burden of shame" is concerned. As Greybeard's answer suggests, both UB40 and the LGBTQ community—to the extent that they may have contributed to the repopularization of "burden of shame" in recent decades—are nevertheless several centuries too late to claim coinage rights to it.