Service composition and optimal selection (SCOS) concerns the building of optimal composite service by integrating existing services with the aim of performing complex task. Due to a plethora of affordable cloud services providing similar functionalities while differing in quality of service (QoS), how to determine suitable candidates to orchestrate the best composite service, also known as QoS-aware SCOS problem, becomes more complicated. A number of evolutionary optimizers have been developed to resolve SCOS. Unfortunately, a large majority of these optimizers carry out the optimization by aggregating many diverse QoS attributes into a single objective or simply considering two or three representative QoS attributes. SCOS, particularly, from the perspective of many-objective optimization, has not received an appropriate attention. As more factors come into play, SCOS is strictly a many-objective problem. This study explores the scalability of recently state-of-the-art evolutionary many-objective optimization (EMaO) algorithms in addressing SCOS. Comparative results reveal that these EMaO algorithms, never before applied to many-objective SCOS, exhibit distinct search abilities with respect to the objective space dimensionality and problem scale. Based on the empirical observation, useful suggestions and insights for choosing suitable EMaO algorithms pertaining to different SCOS problems are given.