A search for muon neutrinos from Kaluza-Klein dark matter annihilations in the Sun has been performed with the 22-string configuration of the IceCube neutrino detector using data collected in 104.3 days of live time in 2007. No excess over the expected atmospheric background has been observed. Upper limits have been obtained on the annihilation rate of captured lightest Kaluza-Klein particle (LKP) WIMPs in the Sun and converted to limits on the LKP-proton cross sections for LKP masses in the range 250-3000 GeV. These results are the most stringent limits to date on LKP annihilation in the Sun.