It's no surprise that 'tuckered out' is an American phrase. No 'B-feature' western from the 1930s and 1940s was complete without Gabby Hayes being 'plumb tuckered out'. Hayes' contribution to the genre was celebrated by Mel Brooks in the 1974 film Blazing Saddles. In that, a look-alike actor played the part of Gabby Johnson, spouting 'authentic frontier gibberish' - "dad gum it, I am gonna die here an' no sidewindin bushwackin, hornswaglin, cracker croaker is gonna rouin me biscuit cutter".
An example is from the Wisconsin Enquirer, April 1839:
"I reckoned to have got to the tavern by sundown, but I haven't - as I'm prodigiously tuckered out."
'Plumb tuckered out' is somewhat later and the first example is from the Cedar Rapids Evening Gazette, February 1889: "They'll get plumb tuckered out waitin."
The actual derivation of this phrase is quite prosaic. 'Tucker' is a colloquial New England word, coined in the early 19th century, meaning 'to tire' or 'to become weary'. 'Tuckered out' is just a straightforward use of that. 'Plumb' is just an intensifier. 'Tuckered out' is rarely seen alone.