Kicking and Korea
Original Karate kata do not contain many kicking techniques. While modern Karate as a martial art contains much more than this, the kata themselves only contain front kicks (occcasionally jumping), side kicks, and the occasional crescent kick into the palm. The kicks are always done one at at time, and never in combination.
Taekwon-Do, on the other hand, has a strong association with kicking. This is a link that the designers of modern Korean martial arts have fought hard to promote since their inception. This can be seen especially in modern Olympic style sparring, though it is very present in all styles of Taekwon-Do.
The Chang Hon patterns were once criticized for looking too much like Karate kata, and a quick tour of this website would suggest that a similarity exists. In the Kukkiwon, this led to the creation of the Pal Gwe poomsae. Later, after these patterns were considered to be too similar to Karate (among other political reasons), they were replaced with the Taegeuk poomsae, which contain more kicking. Later, the American Taekwondo Association (ATA) would develop its own "Songahm" patterns because, as their website explains, the Chang Hon patterns "did not accurately reflect Taekwondo -- particularly the strength and beauty of Taekwondo kicking techniques (emphasis mine)." Some ATA patterns are nearly 50% kicking techniques.
So why must Taekwon-Do be associated with kicking? What about kicking is evidently to essential to Korean martial arts?
Taekkyeon
Taekkyeon was practiced during Korea's Joseon dynasty. Some see it as an ancient Korean martial art, and others as more of a game or sport performed festivals. It is characterized by its use of kicking and takedowns, though modern versions of it tend to be recreations rather than schools with unbroken lineages. It later became associated with criminals and gambling, falling out of favor in Korea when the government turned to Confucianism, and more or less disappeared during the 20th century Japanese occupation. Much of Taekkyeon's real history is clouded by modern myth and legend, so much of this is still widely debated.
The legacy of Taekkyeon is something different. It is an important symbol in Korean martial arts, of something that existed in Korea and nowhere else, and is therefore seen as having a unique Korean quality to it. Almost every modern Korean martial art claims to have some connection to Taekkyeon, some going as far as to incorporate kicking into unrelated grappling styles.
Post-Occupation Korea
The Korean people were told for years that they were inferior to the occupying Japanese, who went out of their way to destroy Korean artifacts and attempted to eradicate Korean culture. Because of this, Korean martial arts were largely wiped out. Imperial Japan used martial arts as a way to spread their cultural influence, not just in Korea, but worldwide (hence the spread and popularity of Judo during this time), and therefore any martial arts practiced by Koreans during occupation were Japanese in origin.
After liberation, the Korean people sought to form an identity for themselves. In this context, Korea's martial artists wanted to form a "true" Korean martial art. Their only experience came from various forms of Karate other Japanese martial arts. A problem then arises when looking purely at techniques, or how to make a punch look "more Korean" or how a stance can be "less Japanese."
Koreans dug into their history for a solution. General Choi Hong Hi writes in 1965 that the name "Taekwon-Do" was chosen because of its similarity to the name of Taekkyeon. And since Taekkyeon was known for its kicking techniques, Taekwon-Do must develop strong kicking techniques in order to provide it with something essentially Korean. Later styles of Taekwon-Do would outright claim that it is based on Taekkyeon, and that Choi's Taekwon-Do is actually Japanese and not "truly" Korean.
It is interesting to see, then, that the incorporation of kicking in Taekwon-Do patterns is not necessarily related to when they were created, but unique kicking tends to show up more towards the ends of the Chang Hon patterns chronologically.
Early Chang Hon Kicking
Take the first three Chang Hon patterns: Hwa Rang, Choong Moo, and Ul Ji. While all Chang Hon patterns are given names for important Korean historical figures, these three in particular were named after important defenders of Korea, and each contain unique kicking.
Hwa Rang:
The Hwarang knights of Korea's Silla dynasty became important symbols to post-liberation Koreans, and they were often associated with Taekkyeon. Choi connects them to Taekwon-Do in the history section of his 1965 book, but whether this association is factual or modern mythologizing is up for debate. Regardless, the kicks in Choi's pattern Hwa Rang are not found anywhere in Karate kata. The roundhouse/turning kicks were not practiced in early Karate, and appear to show up in more recent centuries - in training and competition only, never in kata.
Choong Moo:
Named for Admiral Yi Sun-Sin, a beloved Joseon naval commander who defended Korea from Japanese invaders against impossible odds. The pattern contains a flying side kick and a roundhouse/turning-kick-spinning-back-kick combination.
Ul Ji:
Named after Eulji Mundeok, one of Korea's greatest military heroes, who defended Korea against Chinese invasion. This pattern contains a jumping front kick, jumping back kicks, crescent kicks, and a roundhouse/turning-kick-back-kick combination.
Of the next patterns that make up the first 20, only a handful have noteworthy kicking: Ge Baek's roundhouse kick and jumping sidekick, Ko Dang's back and hook kicks, Yoo Sin's hand-kick-sidekick combination, Choi Yong's roundhouse-hook-sidekick, and Tong Il contains some spinning kicks.
Later Chang Hon Kicking
We know that the last 5 patterns created were Eui Am, Moon Moo, Yon Gae, So San, and (20 years later) Juche. In these final patterns, there is a high concentration of not just kicking, but advanced, difficult kicking.
Eui Am contains 4 "reverse turning kicks."
Yon Gae contains 2 mid-air kicks and 2 "high reverse hooking kicks."
So San contains 2 rotating kicking combinations and a jumping front kick.
Moon Moo has the highest number of leg and kicking techniques of any pattern, including the most difficult.
Juche is ridiculous.
What we end up seeing in the Chang Hon series is not an even distribution of kicking techniques, but a concentration of kicks mostly in the earliest and latest chronological patterns.
To me, this indicates that kicking was an important part of how Taekwon-Do was presented very early in its development. During the next few years, more patterns were created in order to create a full set of non-Japanese exercises. Towards the end of the process, after the first 20 had been established, perhaps it was felt that kicking was not prominent enough in the patterns, so the final 4 (and later Juche) placed a larger emphasis on kicks and were reordered to even out their placement in the series.
Throughout Taekwon-Do's history there have been accusations of different styles "not being Korean enough," and yet it is clear that even the earliest styles sought to distinguish themselves from Karate in different ways, with kicking always playing a role somewhere along the process.
From Choi's 1965 "Taekwon-Do: The Art of Self-Defense"