Of American-English origin, the phrase itchy feet denotes a sense of boredom or restlessness causing a desire to travel, move on or experience something different.

The earliest instance that I have found is from a poem titled De Propah Kind, by Will F. Griffin, published in The Sun (Baltimore, Maryland) on 27^th August 1906:

Ah don’t keer much fer wind sighs dat trickle thru de trees,
Ah don’t keer fer de seashore where dey gits de coolin’ breeze;
De all impohtant question what agitates mah mind
Is how ter get a melon of jest de propah kind.
Ah don’t keer fer de flowahs o’er yander smellin’ sweet,
De country road don’t tease me nor give me itchy feet.
I’so busy cogitatin’ wif a burden on mah mind,
It’s how ter git a melon of jest de propah kind.

The phrase has also occasionally been used with the singular form foot. On 20^th January 1911, The Salt Lake Tribune (Salt Lake City, Utah) published an article about Ollie Dorlon, “the six-day bicycle race champion of 1904”:

Dorlon and his teammate, Eddie Rutt, won the honors at the Madison Square grind of 1904 and straightaway Dorlon got an “itchy foot.” It took four years of wandering to make him ready to get into business with his father, the senior partner of Dorlon & Kennedy, Flatbush building contractors.

As a qualifier of nouns denoting bodily organs, the adjective itching has long been used in metaphorical phrases in the sense that has an irritating desire or uneasy craving. For instance, in Sermons very fruitfull, godly, and learned (London, 1557), the English theologian Roger Edgeworth (died 1560) wrote:

We muste beware that we haue nother itchinge tonges, nor itchinge eares: itching tonges, busy clatering and raylinge, itching eares, euer open and glad to be clawed with newes and noughty tales.

The phrase itching palm denotes a hankering after gain, an avaricious disposition. It is first recorded in The Tragedie of Iulius Cæsar (circa 1599), by the English playwright and Poet William Shakespeare (1564-1616):

(Folio 1, 1623)
– Brutus. Let me tell you Cassius, you your selfe
Are much condemn’d to haue¹ an itching Palme,
To sell, and Mart² your Offices for Gold
To Vndeseruers.
– Cassius. I, an itching Palme?
You know that you are Brutus that speakes this,
Or by the Gods, this speech were else your last.
– Brutus. The name of Cassius Honors this corruption,
And Chasticement doth therefore hide his head.
– Cassius. Chasticement?
– Brutus. Remember March, the Ides of March³ remẽber:
Did not great Iulius bleede for Iustice sake?
What Villaine touch’d his body, that did stab,
And not for Iustice? What? Shall one of Vs,
That strucke the Formost man of all this World,
But for supporting Robbers: shall we now,
Contaminate our fingers, with base Bribes?
And sell the mighty space of our large Honors
For so much trash, as may be grasped thus?
I had rather be a Dogge, and bay the Moone,
Then such a Roman.

¹ condemned to have: blamed for having
² mart: to make merchandise of
³ the Ides of March: the date of the assassination of Julius Caesar by conspirators led by Cassius and Brutus

The obsolete phrase itching elbow denotes a passion for gambling. The following is from The satires of Decimus Junius Juvenalis (London, 1693), by the English poet, playwright and critic John Dryden (1631-1700):

(1754 edition)
Since domestick Examples easily corrupt our Youth, the Poet prudently exhorts all Parents, that they themselves should abstain from evil Practices: Amongst which, he chiefly points at Dice and Gaming, Taverns, Drunkenness, and Cruelty, which they exercis’d upon their Slaves: Lest after their pernicious Example, their Sons should copy them in their Vices, and become Gamesters, Drunkards, and Tyrants, Listrigons, and Cannibals to their Servants. For, if the Father, says Juvenal, love the Box and Dice, the Boy will be given to an itching Elbow.