What communications security protocols exist that aren't based on PKC?
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.