A wireless communications system may include wireless communications devices with each including a wireless transceiver and a processor coupled thereto for transmitting and receiving communications and using a challenge-response authentication protocol. The wireless communications devices may also include a master wireless communications device and a slave wireless communications device. The master wireless communications device may transmit a polling message including an unencrypted portion and an initial encrypted challenge portion. The slave wireless communications device may transmit a polling reply message including an unencrypted portion and an initial encrypted response portion based upon receiving the polling message from the master wireless communications device.