Since the phones require users to be enabled for Enterprise Voice, only Office365 Plan E4 or Lync Online Plan 3 can be used with the Lync Phones as only these plans include the Enterprise Voice" feature equivalent in Lync On-Premise, which is refered to as "Lync-to-Phone" in Lync Online. In US and Canada, the "Lync-to-Phone" PSTN connectivity is provided by service provider JahJah and this service is not currently available anywhere else in the world. For Office365 users outside US and Canada, PSTN connectivity can still be achieved by deploying an On-Premise Lync environment with PSTN connection via a qualified gateway while still using Lync and Exchange Online in the cloud. These are refered to as Hybrid Lync Server deployments. Details on how to configure phones for these hybrid scenarios will be covered in a future article. In this article we will not configure any PSTN connectivity.
For UM to work on the phone, Exchange Online Plan 2 is also required as that includes the UM features that allows the phone to gather call logs and retrieve/playback voice mails. Since Office365 Plan E3 includes Exchange Online Plan 2 but only Lync Online Plan 2, the CX600 phones cannot be used for E3 and attempting to login on the phone using a E3 account results in the error as shown on the right: