Standard paper should have relative permittivity in the range $2-5$, so theoretical capacitance by your given DIY parallel plate capacitor parameters should be $\approx 4~nF$. Multimeters measuring capacitance with $10^2$ order of error likely indicates that measured capacitance is out of range of acceptable values. Same problem is not excluded for more expensive multimeter. So at first you need to find out measurement procedure which overcomes low capacitance measurement problem.
Suggestion is to use "Bridge Technique" to measure capacitance. Basic premise is this,- you take some capacitor with a known calibrated capacitance. Connect this in parallel with your unknown capacitor, with the help of potentiometer. Then calibrate potential drops in the left and right potentiometer arm and find-out your unknown capacitance, which is,
$$ C_X = \frac {R_1}{R_2}C_{ref} $$
In this way, you can measure unknown capacitances, be it very low or very high not supported in your capacitance measurement multimeters. And usually they are calibrated well for measuring resistances in a wide range. Detailed technique and electrical schematics is described in the above given link.
EDIT.
The fact that one of your multimeters gives no reading of whatsoever, gives another idea. That your capacitor may be short-circuited. That is, maybe it's plates are too much tightly pressed towards each other or for other reasons in paper arises micro cracks, so that electrons can go through the paper micro-crack and reach other plate, in such way creating parasitic current and effectively damaging your capacitor.
To resolve and check for this issue. Try increasing number of layers of paper (strengthen dielectric) between the plates- put there $2,3,5,\ldots,$ sheets of paper and then measure capacitance with your "dead multimeter" and see if it becomes alive. If so,- the issue was capacitor plates short-circuiting.
