Solution 1:

According to the OED, this is related to the transitive sense of to pack oneself meant to leave with your belongings, particularly when dismissed. It dates from around 1450.

An intransitive to pack is similarly to depart hurriedly or ignominiously, also from around 1450 in An Alphabet of Tales:

Þis pure man went vnto his howse & stude at þe dure & askid almos; So þis Peirs bad hym pakk & said he sulde hafe none.

And with send, as usually used today, from around 1580 in J. Jeffere's Bugbears:

I sent the knaves packinge.

Solution 2:

From Shakespeare's Henry IV, Part I, 1596:

FALSTAFF: Faith, and I'll send him packing

Found here.

Solution 3:

An even earlier appearance with "send" comes from 1567, appearing in Geoffrey Fenton's Certaine tragicall discourses written out of Frenche and Latin:

"...and after to sende her packinge, and make her passe by the pathe..."

Solution 4:

Searches of Old English Books Online yield fifteen instances of "send [someone] packing" (in one or another form) from before 1580, which is the OED's earliest citation, according to Hugo's answer. They are as follows:

From Certaine Tragicall Discourses Written out of Frenche and Latin, by Geffraie Fenton, No Lesse Profitable then Pleasaunt, and of Like Necessitye to Al Degrees That Take Pleasure in Antiquityes or Forreine Reapportes (1567):

So Tolonyo not ignorant of ye large reuenue, and great summes of moneye of the ladye of CHABRYE, wyth store of other welthe aboute the castel, accompted it a commoditie, to exchaunge the lyfe of hys wyfe, for the fylthie vse of so greate riches, meaning notwythstanding, to enioye the spoiles of so plentifull a praye, and after to sende her packinge, and make her passe by the pathe of so manye morders committed both by the one and thother. Oh vnbridled couetousnes and execrable desyer of vnhonest gaine, howe haste thou blaired the eyes and vnderstandynge of men now a dayes, hardning their hartes agaynst the dread of god, and feare of his lawes?

This is the instance cited by Peter Lukacs in his recent answer.

From a 1568 translation of Dominivus Mancinus, "Of Magnanimitie," in A Plaine Path to Perfect Vertue: Deuised and Found Out by Mancinus a Latine Poet, and Translated into English by G. Turberuile Gentleman:

But he Couragious is and stoute that richesse can despise, / Content with poore and meane estate, where dread nor trouble lies. / Or if he haue the worldly wealth, that so it packing sendes, / As all his ioy consisteth in the aiding of his frendes. / Howe common is the saying of King Pyrrhus vnto those / That came from Rome to ransomhome againe his Romane foes?

From Jan van der Noot, A Theatre Wherein Be Represented as Wel the Miseries & Calamities That Follow the Voluptuous Worldlings as also the Greate Ioyes and Plesures Which the Faithfull Do Enioy (1569):

They labour not to maintain their wife. they seeke not to defēd any against disho∣nestie, rauishment or shame, they desire none for their owne, but when they lust, they take one nowe, and an other to morowe, and then sende hir packing, to haue neither trouble, cost nor charges of hir, nor of the childe, but like vnkyndely Cuckoes lay theyr egges into other folkes nestes.

From a 1570 translation of The Morall Philosophie of Doni Drawne out of the Auncient Writers:

The Lion seeing these beastes on the grounde like drunken chickens, thanked them one by one, saying to the Rauen, that his fleshe was full of yll humors, and if it had bene good he would neuer haue offered it to him: and to the Woolfe also hee sayde, that his was to tough to digest, and at once hee put his deuouring mouth to the throte of the Camell, and set his gripyng talons on him, and tore him in peeces before a man would haue sayde I am here, when the poore wretche thought he should haue escaped with the rest. O God, that fayth assured in wordes commeth to bee broken in deedes: euen so auarice becometh enimye to all honestie. But the best was, the Lyon sent the other beastes packing to the Gallowes and they would, for he would not giue them a bytte to relieue them with, so they died miserably for hunger. Sure a fit death to aunswere so wicked a lyfe.

From An Admonition to Parliament (1572):

For some, & many of the contentes therin, be suche as are againste the worde of God, as by his grace shalbe proued vnto you. And by the way, we cānot but much maruel at the crafty wilines of those mē whose partes had bene fyrst to haue proued eche and euery cōtent therin, to be agreable to the word of god, seing that they enforce men by subscription to consent vnto it, or els send them packing from theyr callings.

From a 1574 translation of Sermons of Master Iohn Caluin, vpon the booke of Iob:

Seeyng it is so with vs that we cannot holde out when God afflicteth vs, but by his power: were it not a greate follye in vs, to desyre therevpon, that his mightinesse should bee a∣bated? Wherefore (as I haue sayde erewhyle,) Let vs learne not to desire that his glory should bee diminished for the easing of vs. For that were the cleane wrong way, and wee should bee vtterly disappoynted of our desire, if we thought too bee eased by the weakening and effeebling of Gods hande. For that were the next way too send vs packing, bycause there is none other meane too preserue vs, but onely Gods vttering of his strength in vs, as I haue sayde afore.

From a 1575 translation of Jean d'Albin de Valsergues, A Notable Discourse, Plainelye and Truely Discussing, Who Are the Right Ministers of the Catholike Church Written Against Calvin and His Disciples:

Thus you see Sirs, that both the Scripture and Miracles were necessarye for the confyrmation of the comming of Christe amonge the Iewes, who were neuer harder of beliefe then we are, according to your opinion: and therefore blame vs not, if we sende you packing like Coggers of the Scriptures, the which doo neither beare witnes of your comming, nor yet doo any miracles, the which two things and more are necessary to make vs beleue your reformed Gospell.

From Thomas Newton, A Notable Historie of the Saracens Briefly and Faithfully Descrybing the Originall Beginning, Continuaunce and Successe aswell of the Saracens, as also of Turkes, Souldans, Mamalukes, Assassines, Tartarians and Sophians (1575):

There was a certayne Begger, an Armenian borne, whiche could well vnderstande and speake the Arabian language. This poore Armenian begging the charitable almes of the Arabians which lodged abroad without the Citie, chaunced to heare one of them in the Chestes asking an other of his fellowes where they were, and immediatlye departinge from them went into the Citie, and discouered this trecherous traine to the Prouoste. Who by this meanes hauing ynckeling and intelligence thereof, left the Princes of the Arabians banquetynge and making good chéere in the Citie, and with a conuenient number of Citezens issued out of the Gates, and openinge the Chestes, kylled all the armed men in the same. And comming back againe into the Citie, killed also all the Princes and Capitaines of them, sauing onely one, whose two handes he chopped off, and curtaylyng his nose and eares, sent him away packinge with a Flea in his eare, to carry news home of their good spéede and aduenture.

...

The great Turke besieged Croia a citie of Aemathia, many Monthes, but by the worthy prowesse of Scanderbeg, he was defeated from his purpose, and with losse of many of his men was sent away packing with a Flea in his eare.

From John Hooker, Orders Enacted for Orphans and for Their Portions within the Citie of Excester with Sundry Other Instructions Incident to the Same (1575[?]):

This Echinus [a hedgehog], was contented to yeld to all conditions, and promised to parfourme all couenaunts, but being once entred in to the [serpent's] howse: it was not long before he had forgotten all promises, and practiseth all the waies he may: how to obtaine his purpose, wherfore he buskleth vp himself, and by litle and litle goeth about the house, & at length ful boldely seeketh euery place, and sercheth euery corner, but the Serpent, whose dainty and soft skin could not abide the sharp prickles of this churlish hedge hog: is driuē to leap from corner to corner and notvvithstanding she hisseth at him, and challenging her promises: dooth burden hī with vnkīdnes, yet it auaileth not, for she is so long driuen from corner, to corner: and from place to place, that at length she is clene shifted out of the doores & sent packīg to seek a new lodging.

From a 1577 translation of The Ecclesiasticall Historye of Socrates Scholasticus:

I truely did neyther talke with him at that time, neyther reason of any circumstance. And when he entreated, that I woulde geue him the hearing, I was so farre from it, that with the deniall, I had almost caused him to be sent packing, with rough entertainment. His sute was nothing else, but that all you might be brought thither, to the ende he might in our presence expostulate face to face with you, the iniurie he suffred necessity driuing him thereunto.

...

But it is plaine it could not be so, for Nestorius was commaunded vnder paine of an accurse not to shewe his face in the councell. The which thing also Eustathius byshop of Berytum writeth plainely in the letters which he sent to Iohn the byshop & to another Iohn the priest, of the canons laid downe by that councel. his words are these. There came to this councell such as diligently searched out for the reliques of Nestorius and with open mouthes they exclaimed vpon the councell: what reason and conscience is there that holy men shoulde be accursed? So that the Emperour was greatly incensed against them and commaunded his gard they should send them packing with a vengeance. Wherefore I can not see how Nestorius after his deceasse should be called to the councell.

From Raphael Holinshead, The Firste [Laste] Volume of the Chronicles of England, Scotlande, and Irelande (1577):

These Bishops with other to them associate, made instant request and sute to the king for the obseruing of the Popes commaundement, and to eschew the censures of the Church: but that was in vain: for the king in a great rage sware, that if eyther they or anye other presumed to put his lande vnder interdiction, he would incontinently therevpon sende all the Prelates wythin the Realme out of the same vnto the Pope, and sease all theyr goodes vnto his owne vse.* And further he added, that what Romaines soeuer he founde within the precinct of anye his dominions, he would put out their eyes, and slit their noses, and so sende them packing to Rome, that by suche markes they might be knowne from al other nations of the world.

From a 1578 translation of Estienne de Maisonneufve, The Gallant, Delectable and Pleasaunt Hystorie of Gerileon of Englande Containyng the Haughtie Feates of Armes, and Knightlie Prowesse of the same Gerileon, with his Loues and Other Memorable Aduentures:

I knowe not what thou wilt dooe (saide the Knight) but garde thy selfe well from mee, for I meane to sende thee packyng with hym whom euen now so rashely thou hast slaine. Oho (saide the Giant) in mockyng wise, seeyng hym come with a speare, couched in Reste against hym, see here a retchelesse boye: but scarse had he so saied, but that the Knight had striken his Launce twoo foote and more within his body, wherewith he fell to the grounde: neuerthelesse he soone rose againe, and came to haue killed his horse, nothing remembring his promise made to his brother.

From a 1579 translation of Philips van Marnix van St. Aldegonde, The Bee Hiue of the Romishe Church a Com[m]entarie vpon the Sixe Principall Pointes of Master Gentian Heruet, a Romish Catholike His Booke:

Also, wherein soeuer the decrees may further her purpose, she may haue them in reputation, and make them equall with Gods worde. But whensoeuer the Scripture doth make against her, she may finde a glose, or an Allegorie vpon it, and so couer the matter with a blewe mantle. And when the olde Fathers write any thing, which soundes against her holines, she may thrust them out of the doores, and send them packing. And wherein soeuer she doeth mislike of the Councels, she may admit & approue other councels against them, and so driue one thunder away with another.

From a 1579 translation of Andreas Hyperius, The Course of Christianitie: or, As Touching the Dayly Reading and Meditation of the Holy Scriptures:

Hierome maruelleth, and stomacketh the matter, and counteth it intollerable, if anye man shoulde so presume. Forsomuch (saith he) in the proheme of his exposition of the Epistle of Saint Paule to the Ephesians, as we differ from all other creatures in this point chiefly, that we are endued with reason, and haue the vse of speaking: and al reason and holy speach is contayned in the bookes of God, by which we both learne to know God, and also to what ende wee be created: I maruaile greatly at some, who, either giuing themselues to slouthfulnesse and slepe, wil not learne the things that are excellent, or else seeke to reproue others, that bend themselues that waye. Which men whereas I might more straightly stop their mouths, & shortly send thē packing either eased or plea∣sed, in vouching that it is much better to reade the Scriptures, than to gape so greedily after the encreasing and hourding vp of riches: I will content my selfe onelye in saying this, whiche I maye obtaine euen before a moste incompetent Iudge, namely, that my vocation from labor, and quiet solitarinesse of mind, is more pleasant vnto me, than al other solemnities whatsoeuer. Hitherto Hierome.

And from a 1579 translation of Plutarch, Lives of the Noble Grecians and Romanes:

For they [pirates] clapped their handes on their thighes, and fell downe on their knees before him, praying him to forgeue them. The poore prisoner thought they had done it in good earnest, seeing they humbled them selues as though they seemed fearefull. For some of them came vnto him, & put shooes on his feete: others clapt a gowne on the backe of him after the ROMANE facion, for feare, (sayd they) least he should be mistaken an other time. When they had played all this pageant, & mocked him their bellies full: at the last they cast out one of their shippe ladders, and put him on it, & had him go his way, he should haue no hurt: and if he would not goe of him selfe, then they cast him ouer the bord by force, and sent him packing.

...

[A]nd short∣ly after that, he [Hannibal] came with two thowsand horse so neare vnto ROME, that riding from the gate Collina, vnto Hercules temple, he had leysure to view at this pleasure, the situation and walles of so great a citie. Fuluius Flaccus seeing that, could not abide it, but straight sent out certen men of armes of the ROMANES against him: who comming with great furie to giue charge vpon him as they were commaunded, they easily sent him packing.

All of these instances seem reasonably consistent with modern figurative use of "send [someone] packing": to dismiss, banish, or drive away. If so, the meaning of the expression has been remarkably stable over the past 450 years.