Narodil se 5. září 1941 Věře Ždichyncové, tanečnici, která základy získala u Emericha Gabzdyla v Ostravě a v roce 1948 nastoupila do Národního divadla v Praze do souboru ještě pod vedením Saši Machova. V matčiných šlépějích šel Pavel Ždichynec od malička. Nejprve navštěvoval Baletní přípravku Národního divadla, poté úspěšně složil přijímací zkoušky na taneční oddělení Pražské konzervatoře, po absolutoriu působil v rámci vojny v Armádním uměleckém souboru a v roce 1963 nastoupil do Národního divadla, kde se v letech 1966–1983 setkával i s maminkou v roli baletní mistryně.
Sólistou se Ždichynec stal v roce 1966 a jako takový působil po boku Miroslavy Pešíkové, Anety Voleské (která se stala jeho životní partnerkou), Michaely Vítkové nebo Marty Drottnerové na jevišti až do počátku 90. let, kdy se stal nakrátko šéfem Laterny magiky.