What happened to the rename song iTunes keyboard shortcut

Just use Tab.

If you start with the focus on the playlist and hit Tab, the focus will go to the sidebar. You can start typing Mus and the Music library will display in the main panel. Hit Tab again. The focus will jump to the search bar. Start typing the song you're looking for. Hit tab again and you're back in the main window where you started.

You can use OptionCommand + f to jump to the search box at any time regardless of where the focus is.

It sounds like you'd benefit from an app launcher with built-in iTunes launch/search navigation. Quicksilver and LaunchBar are both good choices.

fn + return works while navigating with the up and down keys. Edit the song, then press return again to submit changes.

For the other columns just press tab to reach the desired column.