Something that is 'toe-curlingly embarrassing' is discomforting enough as to make one squirm and curl one's toes in response.
The date of origin of this American phrase is rather uncertain. In 1901, George Ade published his humorous 'fractured fables' Forty modern fables. This contains an allusion to toe-curling in the sense of embarrassing:
"When they struck a Barber-Shop Minor they would Dwell until the unhappy Listener felt his Toes curling."
That isn't an example of the precise phrase as we use it now, but is is clearly not far away.
'Toe-curling' was a common phrase in the USA in the 1950s but it was used to convey a sense of pleasure rather than embarrassment. There are many advertisements from around that time that refer to deep-pile carpets or blankets that offered "toecurling warmth" etc. Another, more figurative, example comes from the letters page of the California newspaper The Oakland Tribune, July 1950:
I was perfectly content with, "Gee, I love you, Freckle-Face," until that awful person had to go and inform me that only old fogies with one foot in the grave and the other on a banana peel didn't give out with poetic, dynamic and toe-curling phrases like "Your eyes are like limpid pools - Your lips are like etc." My husband NEVER said things like that to me.
'Toe-curling' in the sense of embarrassing isn't found until the 1960s and so is probably derived independently of Ade's version. The Jamaican newspaper The Gleaner, printed this in November 1962:
"I recall disgracing myself into flushing, toe-curling nervousness by dropping, and cracking... my huge, much-decorated heavy chamber pot!"