The free energy of a one-component plasma (OCP) in a bcc crystalline state is calculated by a quantum Monte Carlo (MC) simulation method. The partition function in a Feynman path-integral form is sampled over a semiclassical reference system of 128 MC particles, with quantum fluctuations generated according to the Wigner-Seitz model. Exchange effects are shown to be negligible. Helmholtz-free energies of the Coulomb solid, computed at 48 combinations of density and temperature parameters, are decomposed into harmonic and anharmonic contributions and are fitted to analytic formulas; accuracy of the result is confirmed through comparison with the Wigner-Kirkwood expansions and with the ground-state results. The free-energy formulas are applied for calculation of the melting curves in dense carbon and helium OCP materials, appropriate to interiors of degenerate stars, showing that the melting curves start to deviate from the classical predictions at around rho(m) = 2 X 10(8) g/cm3 (C) and 2 X 10(3) g/cm3 (He), far lower than the values predicted by analyses of the Lindemann type.