What's the origin of the purely ceremonial military performances and/or units, like changing of the guard ceremonies or military parades?

Guards units were originally formed as an elite proto-commando force designed to function as a bodyguard for the Sovereign. They were entrusted with his personal care on the battlefield and with his movement around the country. You can think of the early guards of the 16th century as something of a cross between the modern Secret Service and the Marine Corps -- these men were in charge of protecting the Sovereign, but they also functioned as an elite military unit that served the Crown. As a result, many early guards units were also, uniquely, the core of a professional standing army.

As the power of the Sovereign grew with the rise of absolute monarchy and centralization in the early 17th century, so did the size of the guards. A typical case of "guards inflation" is Sweden's Livgardet, which initially began as a body of 16 gentlemen charged with the care of Gustav Vasa.

1521: 16 gentlemen are assigned to Gustav Vasa as personal bodyguards
1523: These 16 gentlemen are merged into the Royal Corps of Halberdiers charged with the protection of the Swedish Royal Family and Tre Kronor Palace
1619: The Royal Corps of Halberdiers is disbanded and the unit is folded into the Household Company which, in addition to protecting the Sovereign and his palaces, accompanies the King throughout Europe
1633: The Life Guards are charged with the defense of the capital and expand into a regiment-sized unit. The following year, all officers of the regiment are required to be noblemen.

Like many guards units, the Livgardet became increasingly specialized over time to the point where we now think of them as exclusively as soldiers rather than actual bodyguards of the Head of State. Ceremonies such as the Changing of the Guard therefore date from an earlier time when the guard changed shifts at strategic points of entry to the palace rather than a public presentation of power.