Is there a way to calculate the difference in pitch required to reach a certain vertical speed?
I'm surprised no-one has attempted to answer this question, as it is mostly a pilot's daily job to guess a pitch change that would give a certain rate of climb. :-)

This will not be a technical answer, but I suspect some of my attempts at controlling the rate can be ported to a PID algorithm.

Keeping math aside, if you draw the lift-drag-thrust-weight diagram, there is probably a tan(x) dependency there between pitch and rate. For the small angles of pitch we are talking here, a linear dependency is good enough on the assumption of tan(x) ~ x . So basically, if I want to half my climb rate, I start by reducing my pitch to half and then I take it from there.

Secondly, the larger planes will still fly by the numbers, so I have a pretty good idea of how 2.5 deg will give me level flight at 250kts, 5 deg will give me around 1000fpm at climb thrust ,etc. I initially pitch to the memorized pitch angle and then adjust as necessary.

Short answer: 

Build a table of pitch vs speed vs climb rates with climb thrust, and a table of pitch vs speed vs descent rates at idle thrust.  Assume linear dependency between pitch and rate. Adjust PID from there. Voila'!