Hey all, who had the same issue and can't reset the device because they can't find the proof of previous connection with the keyboard. You have to go to Devices and Printersin Control Panel, then click Add a Device. You will try to connect to the keyboard through this screen, which will still show you the "Enter a Code to Connect to the Device" message, as well as a new "Or, Enter A Code on the Device" message.
Hope that helps :)
You are the real MVP here. Better than Microsoft Support. They had me try a system restore to a point before the keyboard initially failed to connect. Even that didn't work.
Your answer is EXACTLY what i needed.
Thank you so much!