Is a virtual machine all that's needed to run a small application?

No. A virtual machine requires a set of core libraries to run applications. Some of these libraries are packaged as a part of a CLDC implementation along with the virtual machine. In addition, the capabilities of CLDC can be extended by adding profiles such as the Mobile Information Device Profile (MIDP) and/or optional packages.