The first explicit historical mention of a war that I know of dates
from c. 2800, when Aha of Egypt is entitled with vitories over Nubians
and Lybians and maybe over Northern Egyptians as well. His successors
Djer and Uadjy also campigned out of Egypt. Udimu (Den) is shown
fighting against Asians.
C. 2700, Snefru of Egypt left records of campaigns in Nubia, returning
with 7,000 prisioners and 200,000 cows, against Lybia, capturing 11,000
men and 13,100 cows.
In Sumer, c. 2700 BCE, Enmebargesi or Mebaragesi of Kish, is the
firsthistorical king mentioned at war: he fought "victoriously" against
Elam. His son, Agga, fought against Gilgamesh of Uruk, without success.
The Royal List states: "Kish was abated by the force of arms, royalty
was transfered to Eanna", the temple of Uruk.
In an unclear but seemingly earlier moment, other registries, mention
that Enmerkar of Uruk had to fight aganits the Martu (Semites), who
even besieged Uruk once. Here we find a clear mention of a specific
bellic episode or battle: the siege of Uruk by the Martu. This Enmerkar
is antecessor of Gilgamesh, so the even had to happean earlier than the
previously mentioned dates. The siege of Uruk could then be the first
recorded battle, even if its description is vague.
Another king of Kish, Mesalim, launched a campaign into Syria,
destroying Ebla, a major rival. This seems to have happened c. 2600,
during the hegemony of Uruk. This one could be the first recorded major
campaign.
C. 2550 Uruk "is defeated by arms, royalty passed to Ur"
There are other sumerian mentions of wars and related episodes: Lagash
fought for its borders against Ur and, specialy Umma, capturing one
king of this city (Pabilgaltuk), who was executed.
C. 2450, Elam launched a major campaig, campuring Kish, what caused all
Sumerian cities to movilize against it. Eannatum of Lagash defeated the
invaders and destroyed Susa, the Elamite capital. Then he defeated
Mari, captured Umma, Ur, Uruk, Ki-utu and Kish.
Despite all these struggles and victories the more clearly recorded is
the old dispute with Umma on strategical border issues. It seems that
Eannatum benefitted from his power in the dispute of Lagash, what
caused Ush (or Gish) of Umma to attack him. Eannatum soon defeated the
Ummaites, killing 3600 enemies, who he ordered to bury in 20 large
mounds. Umma then rebelled and killed Ush, what allowed for peace. The
stele of ravens narates this Lagash*te victory.
Meanwhile, in Egypt, Sahure' and other monarchs of the 5th dynasty are
recorded campigning in Nibia, Lybia and Sinai. Same did Pepi I, third
pharaoh of the 6th dynasty, c. 2300, who sent expeditions to Nubia and
Asia.
At this same time, Sargon or Sharrukin of Akkad is entitled not just
with many campaigns, including the conquest of Uruk and dismantling its
defenses but also with the stabilishment of the first historically
recorded Empire after Egypt.
Yet, according to
Wikipedia, Kadesh is the first documented battle as such.