early 13c. (c. 1200 in Anglo-Latin), "stake, pole, stake for vines," from Old French pal and directly from Latin palus "stake, prop, wooden post" (source also of Spanish and Italian palo), which is from PIE *pakslo-, suffixed form of root *pag- "to fasten." A doublet of pole (n.1).
From late 14c. as "fence of pointed stakes." Paler as a surname meaning "fence-builder" is recorded from late 12c. Another Middle English form of the word in the "fence, paling, wall of an enclosure" sense, based on the plural, was pales, palis (late 14c.), and the surname Paliser is attested from early 14c.
The figurative sense of "limit, boundary, restriction" is from c. 1400, and survives (barely) in beyond the pale and similar phrases. Meaning "the part of Ireland under English rule" is by 1540s (the thing itself dates to the conquests of Henry II), via the notion of "enclosed space," hence "district or region within determined bounds," hence "territory held by power of a nation or people" (mid-15c.).