C340, your profile doesn't indicate your aircraft type, but I'm guessing that it's A340 from your call-sign. I don't fly the A340, but I'm assuming that, like most other aircraft of it's generation, that it does have Flight Path Indicator / Flight Path Vector Indication. FPV is indicated in degrees, and to convert from Gradient in % to degrees, multiply by 0.6,
e.g. 5.0% X 0.6 = 3.0 Degrees
If you then fly to, or observe as a minimum the FPV you will meet the requirements.
NOTE - 0.6 is not quite correct, but very very close and slightly on the CONSERVATIVE side, the 5.0% used in my example is actually 2.9 Degrees.
I regularly use FPV to satisfy Gradient requirements in SIDs, and for Non-Precision approaches where a Descent Gradient is quoted. Being Inertial it's extremely accurate and instantly responsive.
The problem of dual minima into Thessaloniki that you quoted is one that we often see into, for example, Hong Kong 25R, where the (Right Turn) missed approach is over very high terrain, and the ILS DA very much higher if unable to meet the gradient from the normal DA (I don't have the chart with me, sorry, no figures). My operating policy is to refer to the AOM/QRH to ascertain climb gradient capability, and if unable to use the 'normal' DA, operate to the higher DA. If a missed approach after the DA should become necessary (loss of visual, engine failure etc.), operate to the (Left Turn) Engine Failure Escape Route.