We present constraints on both the kinetic temperature of the intergalactic medium (IGM) at z=8.4, and on models for heating the IGM at high-redshift with X-ray emission from the first collapsed objects. These constraints are derived using a semi-analytic method to explore the new measurements of the 21 cm power spectrum from the Donald C. Backer Precision Array for Probing the Epoch of Reionization (PAPER), which were presented in a companion paper, Ali et al. (2015). Twenty-one cm power spectra with amplitudes of hundreds of mK^2 can be generically produced if the kinetic temperature of the IGM is significantly below the temperature of the Cosmic Microwave Background (CMB); as such, the new results from PAPER place lower limits on the IGM temperature at z=8.4. Allowing for the unknown ionization state of the IGM, our measurements find the IGM temperature to be above ~5 K for neutral fractions between 10% and 85%, above ~7 K for neutral fractions between 15% and 80%, or above ~10 K for neutral fractions between 30% and 70%. We also calculate the heating of the IGM that would be provided by the observed high redshift galaxy population, and find that for most models, these galaxies are sufficient to bring the IGM temperature above our lower limits. However, there are significant ranges of parameter space that could produce a signal ruled out by the PAPER measurements; models with a steep drop-off in the star formation rate density at high redshifts or with relatively low values for the X-ray to star formation rate efficiency of high redshift galaxies are generally disfavored. The PAPER measurements are consistent with (but do not constrain) a hydrogen spin temperature above the CMB temperature, a situation which we find to be generally predicted if galaxies fainter than the current detection limits of optical/NIR surveys are included in calculations of X-ray heating. ; Comment: companion paper to arXiv:1502.06016; 10 pages, 6 figures