Note that if you just set the Microsoft Key Distribution Service to Automatic, it will end up being set to Automatic (Trigger Start). The default trigger has created problems for AD FS startup (for me and maybe others too). You can query the trigger configuration by running the sc qtriggerinfo kdssvc command. The default for the Microsoft Key Distribution Service is using an RPC trigger which will start the service when a request is received on the interface. In my testing, I still run into trouble with the AD FS service starting up.
The workaround that I found to be consistent is changing the trigger configuration so that it relies on a different trigger. The command to use is sc triggerinfo kdssvc start/networkon which starts the service when the network is on (typically very early in the boot cycle).
I also tested removing the trigger completely but that wasn’t effective at all.
If you have AD FS installed on the DC running 2012 R2 and use a gmsa for the service account, set the kdssvc to auto (instead of manual trigger) and restart the DC. You’ll find this fixes this issue. You should no longer have a recurrence.
Please report back if you do