The songs must be in your iTunes library first. Don't get confused with the LW playlist that appears within iTunes. Those songs are not within your actual iTunes Music Library folder but instead, still in your LW downld folder. See
How to transfer music to my iPod (& iTunes) As Only A Hobo said, there's no reason to convert any songs. Just import them into your iTunes library & then send them to iPod from there. iPod will recognise both mp3 & m4a & more types.