There's a script for that: Steps for renewing NDES Service Certificates

Well this was a life saver once again, being on vacation the moment this was implemented, and the supplied documentation by the 3rd party that did that being insufficient, this saved my a s s.
And as stated by the blogger "chdelay" there's not a lot of info to be found on this matter.

For those organizations that used the Network Device Enrollment Service run into the process for renewing the certificates for NDES. I never was able to find good instructions on how to do this. So, I had no choice but to create my own. The steps in this blog posting cover how to renew the certificates used by the Network Device Enrollment Service. You will need to be logged in as an Enterprise Admin for most of the steps outlined in this posting.

Step 1: First give the NDES Server Read and Enroll permission to the CEP Encryption Certificate Template.

Step 2: Open the certificates MMC targeted to the computer. Expand Personal. Right-click on Certificates. From the context menu select All Tasks then Renew Certificate with New Key…

Step 3: On the Before You Begin page of the wizard, click Next.

Step 4: On the Request Certificates page, click Enroll.

Step 5: On the final page of the wizard, click Finish.

Step 6: Open Certmgr.msc as a user that has Read and Enroll permissions to the Exchange Enrollment Certificate Template. Expand Personal, right click on Certificates. Select All Tasks, and then Request New Certificate…

Step 7: On the Before You Begin page, click Next.

Step 8: On the Select Certificate Enrollment Policy page, click Next.

Step 9: Select the Exchange Enrollment Agent certificate template, and click the More information is required to enroll for this certificate. Click here to configure settings. link.

You will want to user the same Subject Name that is in your current Exchange Enrollment certificate. The following steps illustrate the steps needed to do this. You can find the current subject name by opening the Certificates MMC targeted to the local machine and then open the existing Exchange Enrollment Agent certificate. In my example the name was CN=FCNDES01-MSCEP-RA,C=US.

Step 10: Under Subject Name ensure that Common Name is selected and under Value enter the common name that is in your existing certificate. Then click Add.

Step 11: Change the Type to Country and under Type the country code that is your existing Exchange Enrollment Agent certificate.

Step 12: Click Add

Step 13: On the Private Key tab, select Make private key exportable. Then click OK.

Step 14: Then click Enroll.

Step 15: Right-click on the Exchange Enrollment certificate in the users personal store. Select Export…

Step 16: When the Certificate Export Wizard opens, click Next.

Step 17: On the Export Private Key page, select Yes, export the private key.

Step 18: On the Export File Format page, select Personal Information Exchange – PKCS #12 (.PFX)

Step 19: On the Password page, enter a password and click Next.

Step 20: On the File to Export page, click the Browse… button. Select the file name and save location. When finished click Next.

Step 21: On the final page of the wizard, click Finish.

Step 22: Then click OK.

Step 23: In the Certificate MMC on the NDES Server that is targeted to the computer, expand Personal. Right-click on Certificates. From the context menu, select All Tasks and then Import…

Step 24: On the Welcome page, click Next.

Step 25: Browse to the PFX file you previously created, and click Next.

Step 26: On the Password page, enter the password associated with the PFX file.

Step 27: On the Certificate Store page, click Next.

Step 28: On the final page of the wizard, click Finish.

Step 29: Then click OK.

Step 30: In the Certificate MMC on the NDES Server that is targeted to the computer, expand Personal. Right-click on the old Exchange Enrollment certificate, and select Delete.