I've returned to writing by hand increasingly over the last couple of years, after a couple of decades of rarely holding a pen. To start with, my handwriting was barely legible, and my hand painful after a couple of sentences. Now I write comfortably and legibly. My advice would be:
- as several others have written, slow down. This is by far the most important to start with. If you really needed to record something quickly, you wouldn't be handwriting. So accept it's going to be slow.
- consciously relax your writing hand and arm, where by consciously I mean quite literally reminding yourself, and tensing/relaxing the hand and arm to cement the physical sense of what the relaxed limb feels like. This helps with the cramping/pain
- if legibility matters for your purposes, find the letter forms you write most poorly. Read some of your handwriting, find the words you stumble over, and identify the letters causing this. Show someone your writing and ask them if you're not sure (for me it was 'o' and 'e' - in both cases I wasn't keeping the loop open). Now find a new more legible form for these letters, and use the new form as often as you can remember. In my case I reversed the loop direction I had learned for the 'o' (the physical difference concentrated my mind on keeping it open).