Two-dimensional path planning for unmanned underwater vehicles (UUVs) often presents challenges such as nonlinearity, multiple constraints, and non-convex search spaces. The efficient and safe generation of autonomous trajectories has become a critical scientific issue for improving platform reliability and operational efficiency. This paper introduces a parallel information exchange mechanism and a local mapping strategy into the classical Artificial Protozoa Optimizer (APO) framework, and proposes a novel parallel APO-based metaheuristic algorithm with Lévy mutation, termed PAPO-LM. The algorithm uses a cooperative search and dynamic scale mapping to avoid getting stuck in local optima in hybrid and combinatorial optimization tasks while keeping running costs low. Experiments based on the CEC 2022 benchmark functions and typical UUV simulation scenarios demonstrate that PAPO-LM outperforms existing methods in escaping local optima, minimizing path length, and ensuring convergence stability, thereby validating its engineering applicability and robustness in complex underwater environments.