Learn English – the origin of this triplet: Time, Talents, and Treasure

I think the origin of these phrases is from Shakespeare's The Merry Wives of Windsor, 1602:

As for which came first, lucky or charm, I found the charm variation earlier and not of American origin as The Phrase Finder has, but British. This is from The Cabinet Album, 1830 (date check):

And the lucky version I found three years later in The Port Admiral, by William Johnstoun N. Neale, 1833 (date check):

Since these two variations can be traced back to the same time period and the same country, I think it's safe to say they are related and that they both echo Shakespeare.

Edit: Heck, why not throw a pretty Ngram in for good measure:

The earliest example I found in Google Books is in Hector Urquhart's introduction to 1860's Popular Tales of the West Highlands:

Practical men may despise the tales, earnest men condemn them as lies, some even consider them wicked ; one refused to write any more for a whole estate ; my best friend says they are all ' blethers.' But one man's rubbish may be another's treasure, and what is the standard of value in such a pursuit as this?

The concept of something having contradictory qualities to different people has been around a long time. "One man's meat is another man's poison" was a 17th century proverb.

Though clearly not the origin of such concepts, here are some 17th-18th century versions. The 1703 The Athenian Oracle: Being an Entire Collection of all the Valuable Questions and Answers in the Old Athenian Mercuries refers to both One's man's pleasure is another's pain and a proverb One's man's meat is another's poison. This book is a bound publication of The Athenian Mercury which ran from 1690 to 1697.

It refers to them in an answer discussing these contrasts and our "perception of what's agreeable to our Natures", or disagreeable. The same could apply to trash/treasure.

Q. What's Pleasure ? What's Pain ?

A. We Answer to both, that 'tis not easie to describe 'em, tho' so easie to know 'em -- and perhaps generally speaking, the more sensible and obvious any thing is, the more a Man may be to seek for a clear Philosophical Notion of it; Science being many removes from singular and sensible Objects, tho' grounded upon them. Besides, what's one man's pleasure is, another's pain, or according to the Proverb, Meat, Poison, and so of the other Senses -- And agen, Pleasure is certainly in some Cases, nothing but Privation of Pain (as Ease after a violent Fit of the of the Stone or Tooth.ach) and the very formality of Pain generally made something Privative or Negative, namely the absence of what's good or pleasant. For a general Description of'em both, which may reach all the Species, and include both body and Mind, we think this following may do -— Pleasure is a perception of what's agreeable to our Natures ---- and Pain, just the contrary, of what's disagreeable or inconvenient -— If any say, this is no more than Pleasur' pleasure, and Pain is pain, we would be oblig'd to them for a more clear and general notion of both those Affections than we have here given.

Just a few years later in 1706 is Several sermons upon the fifth of St. Matthew:

That a thing which is a Sin to one is a Blessing to anther, no more than we count it a Solecism to say, that what is one Man's Meat is another Man's Poison.

And the next year, 1707's A General Treatise of Monies and Exchanges three times gives us a similar phrase to the junk:treasure comparison, in the context of the net wealth of the nation/kingdom/commonwealth remaining the same:

... one private Man's loss in that Case is another private Man's Profit, ...

for one Man's loss becones another Man's Gain;

Very true, Sir, one Man's loss is another Man's Profit;

Some other variations from the early 18th century:

• William De Britaine's 1717 Humane Prudence: "One Man's Fault is another Man's Lesson"

• Daniel Defoe's 1719 The life and surprising adventures of Robinson Crusoe of York, mariner: "Thus, what is one man's safety is another man's destruction"

• Thomas Brown, James Drake, Aristaenetus' 1720 The Works of Mr. Thomas Brown: "One Man's oversight is always another's Gane."

• Nicholas Brady's 1730 Several Sermons: "Estates here often shift their Landlords, and what is one Man's to Day1 is another's To-morrow;"

• William Ellis's 1737 The London and country brewer: "But according to the Proverb, One Man's Mistake, is another's Game."

• Edward Young's 1741 Love of fame, the universal passion: "How one man's anguish is another's sport,"

• A Lady's 1741 The history of Portia: "See what the World is ! one Man's Death is another Man's Joy"

• Leonhard Culmann's 1741 Sententiæ pueriles: "One man's weal is another man's bane. One man's wealth is another man's plunder."