What communications security protocols exist that aren't based on PKC? Lets say that you have two devices that need to communicate in a secure manner. These devices can share secrets before communication takes place (This sharing of secrets occurs over another secure channel). Furthermore, 
these devices can not use public key cryptography.

Assuming that underlying cryptographic primitives are soundly implemented, what communications security protocols exist that can secure such communications at both the message level (authentication, encryption, and integrity) and the protocol level (guard against replay attacks and so on)?
The answer is to your problem is called Transport Layer Security with Pre-Shared Keys (TLS-PSK) and is widely available in implementations.

TLS-PSK offers PKC aided and non-aided key-exchanges, with the former being recognizable by the DHE, ECDHE, RSA parts in their names. This means you want to look for the TLS_PSK_WITH_* cipher suites.

In particular I'd recommend you using TLS_PSK_WITH_AES_128_GCM_SHA256 (or the 256/384 version thereof). If your platform doesn't offer SHA-2 and / or AES-GCM your best choice would be TLS_PSK_WITH_AES_128_CBC_SHA.

Note that TLS-PSK will take care of all the security issues, with the protocol (TLS v1.0, v1.1, v1.2, v1.3, newer versions are preferrable, v1.3: draft version 10 linked) taking care of the protocol level issues using the cipher suites for the message layer issues.