In the first stage of this fight, Kracko is actually invincible. The Star Men are actually meant as a hint for what you need to do - keep climbing up! Kracko will be persistently attacking you and removing platforms, so High Jump is the safest way to make the climb, by continually jumping sky high. Don't wait for Kracko, just keep climbing. Eventually, you'll come across a more decorated platform with clouds, at which point Kracko will get his life bar and the real battle begins.
The climb is possible to accomplish with other skills, but not recommended. Your standard flight is not very fast and Kracko can easily knock you into a pit, or simply make you lose your ability into a pit. If you are insistent, though, Tornado, Hammer, and Throw all make good choices. You'll have to keep an eye on Kracko's movements, and generally do your best to stay on the opposite side of the screen as him.
In the real fight, Kracko isn't too hard, especially with High Jump. The ammo for shooting at him comes from the occasional Star Man that he'll produce (which, of course, you'll probably just use to regain High Jump if you lose it). His other means of attack are mostly to move across the screen with a wave of lightning, or to just charge around the screen directly.
The invincibility of High Jump renders pretty much all of his attack patterns harmless, though. For a non-aggressive fight, stay at the opposite half of the screen (you don't need to hug the corner), and simply jump through him each time he starts an attack or moves across the screen. He'll go down pretty swiftly even without being aggressive.