Ultrasound velocity measurements of magnesium chromite spinel MgCr$_2$O$_4$ reveal elastic anomalies in the paramagnetic phase that are characterized as due to geometrical frustration. The temperature dependence of the tetragonal shear modulus $(C_{11}-C_{12})/2$ exhibits huge Curie-type softening, which should be the precursor to spin Jahn-Teller distortion in the antiferromagnetic phase. The trigonal shear modulus $C_{44}$ exhibits nonmonotonic temperature dependence with a characteristic minimum at $sim$50 K, indicating a coupling of the lattice to dynamical molecular spin state. These results strongly suggest the coexistence of dynamical spin Jahn-Teller effect and dynamical molecular spin state in the paramagnetic phase, which is compatible with the coexistence of magnetostructural order and dynamical molecular spin state in the antiferromagnetic phase.