Is CLDC a virtual machine?

No. CLDC specifies the core libraries and virtual machine features for J2ME implementations on resource-constrained devices. A CLDC implementation includes a virtual machine. For instance, KVM is included in the CLDC reference implementation.