With the urgent requirement of the utilization of renewable energy (RE) for the decarbonization of energy systems, power transmission via high-voltage direct current (HVDC) lines shows limits in the face of fluctuations of RE generation. This paper addresses the coordinated planning of HVDCs and power-to-hydrogen supply chains (P2HSCs) for RE utilization. First, the lumped cluster model of the large-scale power-to-hydrogen is established based on the derivation of the maximum production points. On this basis, P2HSC is modeled as a constrained power load. Then, a multi-objective multi-stage stochastic planning model of HVDCs and P2HSCs is proposed to fully consider RE fluctuation and uncertainty characteristics. Furthermore, a decomposition algorithm based on the dynamic programming method is designed to solve this problem. Finally, the proposed model and algorithm are applied in real Inner Mongolia-Shandong case studies. The effectiveness and robustness of the proposed model are quantitatively verified. Furthermore, the investment interplay of HVDCs and P2HSCs on the planning timeline and the operational interplay of the two sectors as complementary power loads are verified to create the maximum social benefit in renewable energy systems.