It’s not quite accurate to say that “hebrew is supposed to be supported now in both of these programs.” You can get RTL behavior at the character, paragraph, story, and document levels in a variety of different ways in a variety of different apps, going back to CS4.
If you wind up subscribing to Creative Cloud, you can set your language to English (Hebrew) in the Creative Cloud app, then uninstall InDesign and reinstall, and the new install will have all of the RTL tools – because you will have downloaded the ME edition. That will have binding direction toggle in the, um, Page Setup window. If you subscribe, you’ll always have access to both plain-vanilla English and Middle-East versions of ID.
In InDesign CS6, the Middle East edition would be a separate purchase. Sounds like you already have a standalone licence for CS6. I suspect that you can still buy a separate CS6 ME license. Or you can use World Tools, as David suggests – a much cheaper option. Personally, I prefer the World Tools interface in CS6 to the CC Middle East edition, but that’s just a matter of taste, I suppose.
.
