The terms cloud-cuckoo-land and Cockaigne (or the Land of Cockaigne) have similar meanings: a fanciful or ideal realm or domain (cloud-cuckoo-land, OED) and an imaginary country, the abode of luxury or idleness (Cockaigne, OED). The words cuckoo and Cockaigne sound similar, too. But the words are not etymologically linked, apparently.
Cloud-cuckoo-land is more or less a direct translation of the Greek word Νεϕελοκοκκυγία, pronounced nephelokokkygia, which is made up of the Greek words for cloud and cuckoo. This word was coined by the ancient Greek playwright Aristophanes in the 5th century BC in his play The Birds. It referred to an imaginary city in the sky. The first citation for the word in the OED is 1824 in a translation of the play.
Cockaigne was first recorded in Middle English, in 1305 or thereabouts. As regards etymology, the OED says "its derivation has been much discussed but remains obscure". The German linguist and fairytale writer Grimm suggested a link with the German Kuchen (cake), because "the houses there were covered in cakes". Other commentators have linked the word with cake or cook.
In the 1820s London became jocularly known as Cockaigne, because of its similarity to the word Cockney (an old word - see this old post). The composer Edward Elgar wrote an overture entitled Cockaigne (in London Town), which was a musical portrait of London at the beginning of the 20th century.