The phrase overpaid, overdressed, oversexed and over here and its variants were purportedly applied by the British and the Australians to the U.S. soldiers stationed in their respective countries during the Second World War.

These are the earliest occurrences of the phrase that I have found:

1-: From The Dubbo Liberal and Macquarie Advocate (Dubbo, New South Wales, Australia) of Thursday 9^th March 1944:

Disappointment
Several girls were asked to a party to meet some American officers. With them went a woman of 40. The girls seemed to make no impression but the woman received a great deal of attention from a handsome major. Next day a large box of flowers arrived. The spinster was thrilled. This was followed by an invitation to dine and dance.
Coming home in the taxi the major said: “You are asking me in? I want to see your drawings.” (It used to be etchings.)
“I can’t do that,” said his partner. “I live in a flat by myself.” “Well, what of that?”
“In Australia we don’t invite men to our flats at night.”
“Not after the splendid time I’ve given you?”
When they reached the abode the major opened the door of the taxi, pushed her out, and drove off. And that is the last she has heard of him.
A Wisecrack
“The trouble with the Allied servicemen is that they are oversexed,” said a Digger who heard the story.
“Do you know why our men don’t like the Americans?”
“No, why don’t they like them?”
“Because they are overpaid, overfed, oversexed and—over here!”

2-: From the column The Lyons Den, by Leonard Lyons (1906-1976), published in The South Bend Tribune (South Bend, Indiana, U.S.A) of Thursday 20^th April 1944:

In London the story is being told of an American official who was anxious to discover the nature of the British complaints against the American soldiers stationed there. He finally asked one Britisher: “What do you think is wrong with the American soldier?” . . . The Britisher answered: “Well, they’re over-dressed, they’re over-paid, they’re over-sexed, and they’re over here.”

3-: From the column Capitol Stuff, by John O’Donnell (1896-1961), published in the Daily News (New York City, N.Y., U.S.A) of Friday 21^st April 1944:

American troops haven’t worn out their welcome in Australia and New Zealand, but the hospitality of earlier days—when the Jap thrust came dangerously close to the heart of the English-speaking domain down-under—has become a bit threadbare. We asked an Australian the reason the other day and he explained:
“Your troops are over-paid. Furthermore, they’re over-decorated and they’re over-dressed. They’re over-sexed, and damn it, they’re over there.”

4-: From The Mail (Adelaide, South Australia, Australia) of Saturday 29^th April 1944:

Americans Again Are “Over There”
From “The Mail” Special Representative in Britain

London, Saturday.—An Englishman, asked in New York how the Americans were getting along in Britain, replied:—
“Well, everything is splendid but, of course, the Americans are overpaid, over-decorated, over-sexed, and, well, if you must know—
“Over There.”
This story, sent to the “Daily Mail” by its American diarist (Don Iddon) is winning laughs in London, as well as in New York.

5-: From Rank, Pay, S. A. of Yanks Make Tommy Pout, by Howard Whitman, staff correspondent of the Daily News, published in the Daily News (New York City, N.Y., U.S.A) of Tuesday 23^rd May 1944:

London, May 22.—Cafe society of this Yank-infested capital has a new saying which particularly titillates the women. It goes: “There are four things wrong with the Americans. They are over-ranked, overpaid, oversexed and over here.”

6-: From Where is your daughter tonight?, by Eleanor Early, published in the Dayton Daily News (Dayton, Ohio, U.S.A) of Sunday 4^th June 1944—interestingly, the phrase is said to be a “now old gag” and it is a U.S. soldier who applies it to U.S. civilians:

Cecilia was a stenographer in Miami before she got to be a “Big Bruiser” on Broadway. And sometimes she wishes she was still a stenographer.
“Last night,” said Cecilia, “I met a marine back from Tarawa. He said he couldn’t take me anywhere because he was broke, and he told me why service men hate civilians.”
Cecilia giggled. “He said most civilians are wolves. And he repeated the now old gag that wolves are overdressed, overpaid, oversexed—and over here.”

In his column New York Cavalcade, published in The Evening News (Harrisburg, Pennsylvania, U.S.A) of Wednesday 22^nd November 1944, Louis Sobol (1896-1986) wrote that underfed, underpaid, undersexed and under Eisenhower ¹ was used in a British musical as a self-deprecating retort to the phrase overfed, overpaid, oversexed and over here:

New York, Nov. 22.—A little o’ this, a little o’ that! Despite the robot bomb menace London’s rialto is ablaze and currently a top-hit is the lavish musical “Happy and Glorious,” starring Tommy Trinder ², Britain’s own Bob Hope. But in letters reaching this department, none of them too resentful, it appears the big bits of humor are well at the expense of the American boys. Thus there is an Induction Center skit in which a British rookie, getting his uniform, inquires plaintively: “Where are the medals?” to which the supply sergeants snaps: “Wrong Army, bub.”
Another is, “Look at the Yanks—overfed, overpaid, oversexed and over here. And then look at us, underfed, underpaid, undersexed and under Eisenhower.”

¹ In the self-deprecating phrase, under Eisenhower refers to the fact that the U.S. general and statesman Dwight David Eisenhower, 34^th President of the USA from 1953 to 1961, was Supreme Commander of Allied Expeditionary Forces in western Europe from 1943 to 1945.
² Thomas Trinder (1909-1989) was an English comedian.

A variant of this self-deprecating retort occurs in the following about one of the orators at Speakers’ Corner, in Hyde Park, London, from One Man’s Opinion, by W. Earl Hall, published in the Mason City Globe-Gazette (Mason City, Iowa, U.S.A) of Monday 11^th December 1944:

When I arrived in his audience—the largest on the ground, incidentally—he was just in the midst of a gag I had previously heard in London. He was reciting the objections to the American soldier in Britain—overpaid, overdressed, oversexed and—over here! Then he trotted out a sequel that I hadn’t heard.
There are objections to the English soldier too, he said, and proceeded to list them as follows: Underpaid, underdressed, undersexed and—under Eisenhower!