Plesk license key was purchased with CloudLinux key.
Does Plesk register CloudLinux key on the server automatically?
No, CloudLinux license key should be registered manually, despite license being included in bundle with Plesk.
According to CloudLinux documentation register a server with CloudLinux Network using activation key:
Connect to the server using SSH.
Execute the following commands:
# yum install rhn-setup --enablerepo=cloudlinux-base
# /usr/sbin/rhnreg_ks --activationkey=<activation key> --force
Where activation key is like "1231-2b48feedf5b5a0e0609ae028d9275c93"