I've found that the same exercises that basketball players use to improve their jump shots are very effective.
Explosive power
You tend to want explosive power. Most of what we do is kick fast (not just repetitions, but a single kick itself needs to be fast). We need to build fast twitch muscles, that aids in fast contracting of the muscles needed for the kick. We tend to be less concerned with the slow twitch muscles, which is what is needed for gripping power.
So when we want to throw a round house or front kick, we want to activate the Rectus femoris - the front muscles of the upper leg. That opens the knee joint, and we want to do that so quickly as to snap the foot forward.
When we want to issue a hook kick, then the upper rear leg muscles, the Semitendinosus and Biceps femoris, will help bring the lower leg back - the opposite of the front and round kicks.
When we want to throw a crescent kick or an axe kick, then the abductors and adductors (adductor magnus and adductor longus, the lats, etc) all work to contract the muscles to effect this kick.
And so the way to develop these muscles is through plyometric exercises. These are timed and repeated sets of strength and flexibility exercises. You do one set with as many reps as you can properly do, then you repeat that number in repeated sets.
Of course, there are many other supporting muscles, and so there are many exercises you can do. But here's an example of a simple exercise - you'll repeat for multiple sets, and adjust the reps to suit you.
Standing leg lift. Stand feet parallel; lift left leg straight up to the side as explosively as possible. You can add foot weights or use bands to make it more difficult.
Repeat for a full set, then repeat for 2 or 3 sets. You do this for 5 directions: left leg directions are 2:00, 12:00, 10:00, 9:00, and 6:00 positions; right leg is 10:00, 12:00, 2:00, 3:00, and 6:00.
You've lifted 10 reps * 3 sets * 5 directions, or 150 lifts, for the left leg, and similarly for the right.
Technique is extremely important, so be sure your lifts are not swings - you're not using momentum to lift; rather, you're using the leg muscles to lift. Also, maintain your posture - keep the back straight, and don't use the arms to help swing. You can brace yourself against a wall or chair to keep balance. Also, be sure you breathe out on the explosive lift, and breathe in when you return to starting position.
This is but one exercise. You want to find similar exercises for the glutes, the lower abdominals, and lower legs.
Conditioning the leg and foot
Ok, so your kicks are fast. What's going to happen when you kick something? If you're not careful, you'll hurt yourself, whether your kicks are blocked or you kick a kicking bag. So you need to condition the kicking surfaces of the foot and leg. You can do those extreme exercises of kicking trees and flag poles, but in my opinion, those are too extreme and too dangerous. If you're going pro, a trainer will help you here. But for most people, you don't need or want that kind of training. So, you kick heavy bags - nothing more is needed. Here, repetition is key, as well as rest and recovery. Building mild calluses and desensitizing the contact areas is the goal here. Remember, extreme conditioning is going to hurt you in the long run, so don't overdo it. Kicking until you're bleeding only serves to hold you back on the healing, plus you have a lot of cleanup to do. Take it easy.
Developing technique
Of course, none of this is going to help your technique, so, a 3rd exercise is the kicks themselves. Practice your various kicks in different contexts: slow and dynamic, fast and repetitive, and for power. Change it up often. Here, a trainer helps. Every single kick ought to be critiqued for technique, no matter how tiny the correction needs to be. Here, you focus on all the supporting body parts that go into the kick: breathing, balance, arms, head, torso, standing leg, etc. Here, everything counts. You may want to develop exercises for these parts of the body as well. For example, if you issue a roundhouse, but your head dips too far back, then you need to look at why your torso is falling back. So, the lower abs would be the first thing to look at.
About pushups
Yes, pushups are fine - but the right ones are better. Those that are done with plyometrics in mind are best for Taekwondo, kickboxing, and boxing, because there is no grappling here. So clapping pushups are better than standard pushups, because they are plyometric in nature. That explosive movement is what you need.
On the other hand, if you were a grappler, then you want to develop the slow-twitch muscle fibers because you want gripping power, so, standard pushups are better. For MMA fighters, you want to develop both.
We in Taekwondo don't do grappling, so, we tend to not want to do regular pushups. The clapping pushups are better because we prefer to punch. (And, if you really want snappy forms/poomsae/hyung, nothing except plyometric pushups will do. Go for the 100 Pushup Challenge - just do clapping pushups instead.)
Pushups in any of their variants (clapping, knuckle, diamond, one handed, fingertip, wrist, etc) are fine, but you can change it up with different techniques. Have a partner (preferably a lighter child!) stand on your shoulders as you do the pushups. Or do them on a decline. Do them to someone's count - but make the count vary widely in tempo.
We make it fun on occasion, working toward the 100 Pushup Challenge. In this case, the stronger students get into pushup position, but then get their children to do the same - except the kids start out on dad's back.
Having said that, a pushup is not the end-all-be-all for upper arm strength; that's because the arms are not fully developed. Pushups primarily develop shoulders and chest, but you'll want something for arms. Nevertheless, this is out of scope of the question, so I'll leave it there.
The Hundred Pushup Challenge
The Hundred Pushup Challenge Pocket Reference