In War Karl der Kahle wirklich kahl? Historische Beinamen und was dahinter steckt (Was Charles the Bald really bald? Historical epithets and their background), a book by Reinhard Lebe, the author quotes (p. 115 et seq.) from the writings of Burgundian chroniclers -- de la Marche, Chastellain, and de Commynes.
Olivier de la Marche:
Charles is hot-tempered, lively and stubborn... always wants to have
perceptive... polite... high-minded
accustomed to direct his manner and his conduct towards educated conversation, and between play and laughter took pleasure in speaking well and, like an orator, exhorting his loyal retinue to be virtuous.
Charles the Bold, oil painting by Roger van der Weyden (1460). Image credit: via Wikimedia Commons
However, these descriptions are of Charles the Duke of Charolais and crown prince, while King Philip the Good was still calling the shots. In 1456 Charles took over the reins from his ailing father. He soon found himself locked in conflict with Louis XI, the King of France. On 16 July 1465 their armies clashed at Montlhéry near Paris. The Duke's Burgundian forces carried the day in what was said to be an impressive victory over numerically inferior French foes.
Philippe de Commynes:
Before this day matters of war were alien to Charles and he loved nothing pertaining thereto, but his thinking changed afterward. Henceforth he would wage war until his dying day.
Lebe suggests that this was the day that the heir apparent Charles of Burgund turned into Charles the Bold. He writes that Charles fought like a man possessed, driving his men forward, collecting them for one bloody skirmish after another. Again, quoting Commynes:
He received several blows, including a stab in the throat from a sword
but he did not rest until victory was complete. Commynes:
There were none who were capable of bearing up better in toil and trouble than him... Never have I known anyone bolder. Never did I hear him say that he was tired, nor did I detect any signs of fear...
Cross commemorating the battle of Monthléry. A plaque at the foot of the cross memorializes the two highest-ranking royal knights who lost their lives that day in 1465. Image credit: By Ségala pseudo d'Yves Fraysse (Own work) [GFDL (http://www.gnu.org/copyleft/fdl.html) or CC-BY-SA-3.0-2.5-2.0-1.0 (http://creativecommons.org/licenses/by-sa/3.0)], via Wikimedia Commons
To sum up Mr. Lebe, then, Philip de Commynes did an effective job as PR rep for his ruler, but there must have been some factual reality underlying the hype. Charles was not one to stay back in a tent while his troops fought and died, he took part himself. His death in 1477 came on the battlefield, at the end of a clash in which he over-ruled the counsel of his officers and stood his ground against a superior attacking force (in Nancy).
A perusal of the French Wikipedia article on Charles, however, paints a somewhat different picture of that day at Montlhéry in 1465. It says that during a fight marked by inept tactics on both sides, the left flank of the Royal army had turned tail before battle was joined, that Charles "seeing himself as already victorious" gave chase and pursued them far from the actual battlefield, thus missing the action there; and that King Louis had in fact declared himself the victor as he had been able to withdraw his force largely unscathed to within the ramparts of Paris.
That article also quotes de Commynes as writing that ever since that victory, the Duke of Charolais (the future Charles the Bold) was so convinced of his tactical genius that he refused all advice.
UPDATE: It turns out the story is a little more subtle and nuanced than retailed by Mr. Lebe and French Wikipedia. As yet I have not found an online copy of de Commynes' writings. What I have found is a Google e-book version of a 1984 monograph by Emile-Charles Varenbergh titled Mémoire sur Philippe de Commynes. While de Commynes may have been a loyal PR hack during his service for the Duke of Charolais, his writings published after Charles' death exhibit a much more reflective and at times wry tone regarding the exploits of his famous master.
de Commynes recalls entering the service of the Duke as a young man in 1464. He quickly became his friend and confidante. The next year, the Duke rode into battle at the head of an army of "4,000 poorly armed and inept fighting men", with de Commynes always by his side.
As the title of his memoirs -- Memoires de Commynes, ou Fragment de la comédie humaine -- indicates, the chronicler had an eye for the quirky and off-beat. He was a sharp observer of how the best-laid plans can go awry. The carefully thought-out battle plan at Montlhéry was soon thrown to the winds. The French King (Louis XI) had wanted to avoid conflict, yet the conflict took place. The Burgundians had planned on giving their infantry enough rest before the battle but in fact the men had had no rest, and in their eagerness to charge, they trampled over their own archers, giving the enemy time to retrench in safe positions.
In any case the Burgundians profited from lack of discipline in their foes, enabling them to rout the enemy's right flank. But Charles, who had hurled himself almost alone at a large group of them, received a belly wound from a lance as well as a neck wound from a sword. Nightfall then separated the combatants, with the Burgundians camping on the battlefield. During the night, Charles counted his dead and wounded, expecting defeat if the enemy returned in the morning. Luckily for them, the King had beat a retreat during the night. Charles rejoiced in the victory and from that moment would never listen to advice again.
On reading these descriptions, the word that comes to mind is "reckless" more than "bold".
However -- I am now back to reading the French Wiki -- the first recorded instance of a chronicler calling Charles "The Bold" was not de Commynes':
La forte personnalité du duc, que tous les chroniqueurs décrivent
comme un personnage austère, vertueux et impitoyable, pieux et chaste,
animé d'un sens de l'honneur exacerbé, incita ses contemporains à lui
attribuer des surnoms : ils le surnommèrent ainsi le Hardi ou le
Guerrier, voire le Téméraire, terme qu'on rencontre déjà sous la plume
du chroniqueur, évêque de Lisieux, Thomas Basin, vers 1484.
(The Duke's forceful personality, which all the chroniclers describe as austere, virtuous and pitiless, pious and chaste, animated by an acute sense of honor, moved his contemporaries to attach to him a number of epithets: they nicknamed him The Daring, The Bellicose, even The Bold (le Téméraire), a term one encounters as early as 1484 in the writings of Thomas Basin, bishop of Lisieux.)
Nonetheless -- French Wiki continues -- none of the 15th-century chroniclers consistently employ any of these epithets. Instead, "Charles de Bourgogne" is what he was typically called.
Today we know him as Charles the Bold, but the changeover in the name was slow and gradual.
In the 17th century, the Grand Dictionnaire Historique de Louis Moreri devotes an entry to Charles de Bourgogne, "nicknamed le Guerrier, le Hardi ou le Téméraire" (the Bellicose, the Daring, the Bold.)
In the 18th century, Benedictine historian Dom Plancher still calls him Charles le Hardi.
In the 19th century, during the Romantic Age in France and Belgium the epithet "Charles the Bold" took hold... but his 15th-century contemporaries more frequently had attached to him the nicknames Hardi, Travaillant, Guerrier, even Terrible.
SUMMARY: The earliest recorded use of Téméraire to characterize Charles was in 1484 by Thomas Basin. Other epithets stuck to him more closely for a long time. It was not until the 19th century that Téméraire finally became the standard appellation.
Why did this appellation stick and not one of the others? The cause is probably lost in the mists of history. However, given that an ancestor -- Philippe II de Bourgogne -- was already known as "le Hardi", it may have been due to a simple desire by historians to avoid any mix-up between the two.