Trellis shaping (TS) is known as a flexible technique to generate transmit symbols constrained (or controlled) for a particular desired property of communication systems. In our recent results, an application of TS for peak-to-average power ratio (PAPR) reduction of single-carrier (SC) signals has been extensively studied, to show that even a highly fluctuating envelope can be reduced to a nearly constant level. In this paper, we first demonstrate that the performance of the proposed TS in terms of the bit error rate (BER) and PAPR reduction capability strongly depends on the bit labeling. We then propose a new bit labeling for high-order PSK constellation that can efficiently reduce PAPR while achieving BER performance comparable to that of the Gray labeling (GL).