As the first 5G networks are being deployed across the world, new services enabled by the superior performance of 5G in terms of throughput, latency and reliability are emerging. Connected and Automated Mobility (CAM) services are perhaps among the most demanding applications that 5G networks will have to support and their deployment, performance and potential for improvement has been well investigated over the past few years. However, CAM operation in multi-operator environments and the inevitable inter-PLMN handover caused by the inherent mobility of CAM services have not been studied in length. Moreover, the multiple domains, multi-vendor components and inherent high mobility of the cross-border vehicular environment, introduce multiple challenges in terms of network management and dynamic slicing, making Zero-touch network and Service Management (ZSM) solutions an attractive alternative for these environments. The work presented in this study attempts to analyse the requirements for cross-border CAM operation for the five main CAM use cases selected by 3GPP, based on input from key European stakeholders (Network Operators, vendors, Automotive Manufacturers etc.). A detailed analysis and categorization into four categories of the main challenges for cross-border CAM service provisioning is performed, namely Telecommunication, Application, Security/Privacy and Regulatory issues, while potential solutions based on existing and upcoming technological enablers are discussed for each of them. The role of standardization and relevant regulatory and administrative bodies is analysed, leading to insights regarding the most promising future research directions in the field of cross-border CAM services.