These other options work differently than the simple "Edit in..".

The method that does work for you, with CS4, is using Photoshop as a standard external editor by means of a "dumb" interaction. LR does all the work of converting the image into a bitmp and then saving it as a TIFF or PSD. It knows just enough about the other program, to tell the operating system to start the program executable and to pass it the file that has already been created. Then it keeps an eye on the file, watching for modifications saved to it by the other application.

The only compatibility needed between the two programs is: that PS (or whatever) can understand a TIFF or a PSD made by LR; and in return, that PS (or whatever) can save a modified file which LR can display.

The extended options you mention, rely on LR getting PS to get ACR to do all the work of conversion, and then in due course, for PS to take care of file creation too, and furthermore, to tell LR which file has been created where. This is partly because several conversions are involved rather than one; conversions made directly into Photoshop's memory space but not yet onto disk; which is ACR territory.

In order for this more complex interaction to happen, LR needs to be talking to a fully-compatible PS and ACR partnership - which it knows will properly read all its adjustments, and include them in the bitmap information. At present, from LR4, that means either Photoshop CS6 with ACR 7.x - or else (as a special concession), Photoshop CS5 with ACR 6.7. Unless one of those two setups is detected, these forms of interaction are greyed out. Sorry

Yes; though I suppose you don't absolutely need to upgrade - considering that users of other editing programs with LR, have always managed without any of these conveniences. CS4 is a very capable pixel based editor to partner LR, and in that narrow role, does not need metadata or Raw compatibility.

CS5's interaction with LR4 is not one of full support, even with ACR 6.7 - and the prior upgrade policy where it was OK to skip upgrades every so often, is ending soon.

IMO given a free choice, you would be better off with CS6 on compatibility grounds now. Then you have some more time to consider whether you want to keep upgrading PS every version, as well as LR, in perpetuity...