Hi Shovan,
I'll caveat my comment with the statement that I haven't actually tried connecting to EWS on Office 365 yet, but I have done it quite often locally.
From what I have read online (as I will be attempting to connect to a SharePoint 365 site shortly) it is only a matter of changing the URL that you are using in your Webservices to the online EWS endpoint.
https://<ONLINE_URL>/EWS/Exchange.asmx
vs an internal service endpoint which is usually:
https://<EXCHANGE_SERVER_HOSTNAME>/EWS/Exchange.asmx
I don't see why any extra licensing would be required on the CAPA side, and AFAIK there is no additional costs on the Microsoft side for connecting automation tools via EWS.
You would need to have rules in your Firewall that allow communication to the Internet from the Server (or preferably a designated Host) where you will have the job execute.
Hope this helps,
Ian