Bluetooth out of band (OOB) pairing for random address types is not supported on Windows 8.1-based devices.
To resolve this issue, install update 2919355. For more information about how to obtain update 2919355, click the following article number to view the article in the Microsoft Knowledge Base:
2919355 Windows RT 8.1, Windows 8.1, and Windows Server 2012 R2 Update April, 2014
Microsoft has confirmed that this is a problem in the Microsoft products that are listed in the "Applies to" section.
For more information about software update terminology, click the following article number to view the article in the Microsoft Knowledge Base:
824684 Description of the standard terminology that is used to describe Microsoft software updates