How to choose device : CPLD or FPGA ?

CPLDs are very small devices with no dedicated internal rams or multipliers. FPGAs have internal rams and multipliers. CPLDs are very cheap, FPGAs range from cheap to very expensive.

So if you know its a very simple design with no need for any serious maths or storage, stick with a CPLD. Otherwise you will need an FPGA.

As for estimating your LEs, best way is to write the source code and compile it. estimating LEs for designs more complicated than a few gates is dufficult. On the other hand it can be easy to estimate memory and multiplier requirements.