840 EVO performance restoration
First of all, as you already mentioned, the firmware can be updated on a mac, too. So you do not need windows for that. Here is a Manual. It does not mention 840 EVO, but it should be fine. (Maybe EVO isn't mentioned just because the EVO update came out 30 days later than the non-EVO update and the manual wasn't updated after that?)

Secondly, not the cells are decayed, only their content is decayed. And this can be fixed by a rewrite of the data. The first firmware update (from October 2014) only modified the algorithm used to read data (trying to compensate the aging of files). As you indicated, this alone does not completely solve the problem. A refresh of the old data was necessary. This is where the Performance Restoration Software came into play. It just does this (a full rewrite) in order to ensure that there are no old files.

As it seems, the first firmware update wasn't sufficient and the reading of files got again slower the older the files became.

With the second firmware update (in case of 840 EVO it is EXT0DB6Q) Samsung again modified the algorithm but also introduced a recurring (hardware performed) rewrite of all data. Thereby data does not grow old and the explicit Performance Restoration process is not necessary anymore. Instead, the Performance Restoration will be done by the new firmware recurrently when the drive is idle.

If you really want the data to be rewritten immediately, you could clone the drive and copy the clone back to it, I guess. But there should be no need for that.

Source: Various websites, primarily the ssd review. I suggest to give it a read for a deeper understanding. :)

To your question regarding the Advanced Performance Optimization let me quote anandtech:


  The new Magician 4.6 also includes an Advanced Performance
  Optimization feature, which is similar to the performance restoration
  tool that Samsung released earlier. Basically, it's a command that
  tells the SSD to rewrite all of its internal data, which resets all
  cell charges and hence recovers performance. It's merely a
  supplementary tool as the firmware upgrade itself should be enough to
  restore performance, but in case the performance isn't fully restored
  after the firmware upgrade (and some idle time to let the drive
  refresh the cells), the tool can be used to force a cell charge
  refresh.