There's interlocks going both directions. You aren't supposed to be able to shift unless you're pressing on the brake pedal; you aren't supposed to be able to run the starter motor unless it's in park, etc....

The shift lock solenoid is supposed to prevent you from shifting out of park unless you have your foot on the brake. If that's broke, you push a key into the slot so you can move the shift lever. But that doesn't sound exactly right, for what's broke.

The starter interlock is supposed to prevent you from starting if the transmission is in gear. Try this instead of sticking the key in the release slot... Push the shift lever forward, like you're putting it 'further' into park. While you hold the lever all the way forward, try starting. If that works, the starter interlock switch needs to be adjusted.