I think P-RNAV is giving way to RNP-1 under Performance Based Navigation but even if that isn't true, most of your normal procedures have you covered.
— James Albright
The problem with ICAO Doc 7030 is they set out to give us a regional differences document but they haven't updated it in over ten years. So it tells us we need to have B-RNAV, though many of these areas have moved on to PBN standards.
Precision RNAV (P-RNAV) and basic RNAV (B-RNAV)
126.96.36.199.2.1 The provisions in respect of en-route operations, as specified in 188.8.131.52.2.6 and 184.108.40.206.2.7, shall apply to all such operations conducted under IFR on the entire ATS route network as notified by the appropriate authorities in the following flight information regions (FIRs)/upper flight information regions (UIRs):
Amsterdam, Ankara, Athinai, Barcelona, Berlin, Bodø, Bordeaux, Bratislava, Bremen, Brest, Brindisi, Bruxelles, Bucuresti, Budapest, Canarias (AFI area of applicability), Casablanca, Chisinau, Düsseldorf, France, Frankfurt, Hannover, Istanbul, Kharkiv, København, Kyiv, Lisboa, Ljubljana, London, L'viv, Madrid, Malta, Marseille, Milano, München, Nicosia, Odessa, Oslo, Paris, Praha, Reims, Rhein, Riga, Roma, Rovaniemi, Scottish, Shannon, Simferopol, Skopje, Sofia, Stavanger, Sweden, Switzerland, Tallinn, Tampere, Tbilisi, Tirana, Trondheim, Tunis (FL 245 and above), Varna, Vilnius, Warszawa, Wien, Yerevan, Zagreb.
220.127.116.11.2.2 The provisions in respect of precision area navigation (P-RNAV) shall be applied whenever RNAV terminal control area (TMA) procedures, excluding the final and missed approach segments, are used.
Source: ICAO Doc 7030, §EUR, ¶18.104.22.168.2
You used to see these all over Europe and other places, such as Hong Kong. As the world gravitates to RNP-1 for the terminal sector they are becoming a bit more scarce. If applicable, you should see "RNAV-1" or "P-RNAV APPROVAL REQUIRED" annotated on the arrival or departure procedure.
Example P-RNAV Arrival, Warsaw AGAVA 2X, from Jeppesen Airway Manual, EPMO Page 20-24, 29 Mar 13.
Accuracy / performance standards
P-RNAV is defined as RNAV that meets a track keeping accuracy equal to or better than +/- 1 NM for 95 percent of the flight time. This value includes signal source error, airborne receiver error, display system error, and flight technical error. This navigation performance assumes the necessary coverage provided by satellite or ground-based navigation aids is available for the intended operation.
Source: AC 90-96A, ¶4.c.
Aircraft P-RNAV system eligibility
Consider the aircraft eligible for P-RNAV operations, if the AFM or POH shows the appropriate instrument flight rules (IFR) navigation system installation has received airworthiness approval in accordance with this AC or has a statement of compliance to the performance and functional requirements of JAA TGL-10.
Source: AC 90-96A, Appendix 2 ¶1.c.(1)
Part 91 aircraft/operator approval
U.S. part 91 operators present the following documentation to their FSDO: sections of the AFM or POH as appropriate to establish P-RNAV system eligibility; and, evidence of meeting the requirements contained in Appendix 2, sections 3, 4 and 5. The FSDO issues LOA or similar operational approval documentation authorizing P-RNAV operations to part 91 operators. Appendix 2, paragraph 1d provides guidance for operators not able to determine from the AFM or POH that the aircraft system has been approved and installed in accordance with an appropriate FAA AC.
Source: AC 90-96A, Appendix 2 ¶1.c.(2)
U.S. air carrier aircraft/commercial operator approval
Part 121, 125, or 135 operators should present the following documentation to their CHDO: sections of the AFM or POH that establish P-RNAV eligibility. Once the operator has satisfied the requirements described in Appendix 2, sections 3, 4, and 5; the CHDO: issues OpSpecs to reflect Basic Area Navigation (B-RNAV) and P-RNAV approval; and, approves changes to the minimum equipment list (MEL) to account for B-RNAV and P-RNAV operations. Appendix 2, paragraph 1d provides guidance if the operator is unable to determine from the AFM or POH whether the aircraft system is approved in accordance with an appropriate FAA AC.
Source: AC 90-96A, Appendix 2 ¶1.c.(3)
B034 also authorizes an operator to conduct IFR operations in designated European Basic RNAV (B-RNAV) and European Precision RNAV (P-RNAV) airspace.
Source: FAA Order 8900.1, Vol 3, Chapter 18, OPSEC B034, ¶B.
If your AFM or POH has the necessary statement, you have what you need to apply for OpSpec B034 under 14 CFR 135 or an LOA under 14 CFR 91. Otherwise, there are other means listed in AC 90-96A to get approval.
Under 14 CFR 91 you used to need an LOA and the requirement still appears to exist under AC 90-96A and FAA Order 8900.1, Vol 3, Chapter 18, Section 4. But the requirement seems to have gone away a few years ago with inspectors no longer issuing it and the requirement being "decommissioned" in 2020. See the NBAA Article.
Under 14 CFR 135, you will need OpSpec B034:
Advisory Circular 90-96A, Approval of U.S. Operators and Aircraft to Operate Under Instrument Flight Rules (IFR) in European Airspace Designated for Basic Area Navigation (B-RNAV) and Precision Area Navigation (P-RNAV), 1/13/05, U.S. Department of Transportation
B034 Requirement Decommissioned, NBAA March 12, 2020
FAA Orders 8400 and 8900
ICAO Doc 7030 - Regional Supplementary Procedures, International Civil Aviation Organization, 2008
ICAO Doc 9613 - Performance Based Navigation (PBN) Manual, International Civil Aviation Organization, Fourth Edition, 2013
Jeppesen Airway Manual