We investigate channel-coded physical-layer network coding in a two-way relaying scenario, where the end nodes A and B choose their symbols, S-A and S-B, from a small non-binary field, F, and adopt a non-binary PSK modulation. The relay then directly decodes the network-coded combination aS(A) + bS(B) over F from the noisy received superimposed channel-encoded packets. The advantage of working over non-binary fields is that it offers the opportunity to decode according to multiple decoding coefficients (a, b). As only one of the network-coded combinations needs to be successfully decoded, a key advantage is then a reduction in error probability by attempting to decode against all choices of (a, b). In this paper, we compare different mappings between F and the PSK constellation, and prove that many have identical performance in terms of frame error rate (FER). Moreover, we derive a lower bound on the performance of decoding the network-coded combinations. Simulation results show that if we adopt either i) concatenated Reed-Solomon and convolutional coding or ii) low-density parity check codes, our non-binary constellations can outperform the binary case significantly in the sense of minimizing the FER and, in particular, the ternary constellation has the best FER performance among all considered cases.