We present stellar kinematics and orbit superposition models for the central regions of four Brightest Cluster Galaxies (BCGs), based upon integral-field spectroscopy at Gemini, Keck, and McDonald Observatories. Our integral-field data span radii from < 100 pc to tens of kpc. We report black hole masses, M_BH, of 2.1 +/- 1.6 x 10^10 M_Sun for NGC 4889, 9.7 + 3.0 - 2.6 x 10^9 M_Sun for NGC 3842, and 1.3 + 0.5 - 0.4 x 10^9 M_Sun for NGC 7768. For NGC 2832 we report an upper limit of M_BH < 9 x 10^9 M_Sun. Stellar orbits near the center of each galaxy are tangentially biased, on comparable spatial scales to the galaxies' photometric cores. We find possible photometric and kinematic evidence for an eccentric torus of stars in NGC 4889, with a radius of nearly 1 kpc. We compare our measurements of M_BH to the predicted black hole masses from various fits to the relations between M_BH and stellar velocity dispersion, luminosity, or stellar mass. The black holes in NGC 4889 and NGC 3842 are significantly more massive than all dispersion-based predictions and most luminosity-based predictions. The black hole in NGC 7768 is consistent with a broader range of predictions.