Nonlinear magneto-optical Faraday rotation (NMOR) on the potassium D1 and D2 lines was used to study Zeeman relaxation rates in an antirelaxation paraffin-coated 3-cm-diameter potassium vapor cell. Intrinsic Zeeman relaxation rates of gamma(NMOR)/2 pi=2.0(6) Hz were observed. The relatively small hyperfine intervals in potassium lead to significant differences in NMOR in potassium compared to rubidium and cesium. Using laser optical pumping, widths and frequency shifts were also determined for transitions between ground-state hyperfine sublevels of K-39 atoms contained in the same paraffin-coated cell. The intrinsic hyperfine relaxation rate of gamma(hf)(expt)/2 pi=10.6(7) Hz and a shift of -9.1(2) Hz were observed. These results show that adiabatic relaxation gives only a small contribution to the overall hyperfine relaxation in the case of potassium, and the relaxation is dominated by other mechanisms similar to those observed in previous studies with rubidium.