Should I move the furnace upstairs to help cool the 2nd story?
I would only place the unit in the attic if it was a second unit and it avoided ducts running up and down walls. With an attic unit, you have to worry about a clog in the condensate line causing a leak in your ceiling. Access is frequently more difficult and requires a trip through your entire home. As tabun mentioned, it's noisier. You'd also need to run power and refrigerant lines up there, which won't be cheap. You also need to worry about insulating the unit and all ducts since the HVAC will likely be in uninsulated space. 

Replacing duct work will be a huge job without a lot of reward unless the ducts are easy to access. They will have to pull out drywall all over the place to access the lines.

The best solution would be a couple dampers that you can adjust each season to direct air either upstairs or downstairs. You'll need one installed on each outflow from the HVAC, but the line to the attic is frequently a single trunk going up the wall. You also need to make sure your return upstairs is working well. My personal solution has been to replace my return grilles with the hinged style that supports a filter, and then to leave the filter out of the return that needs more heating or cooling.

The air accelerator would help (make sure it only activates during the AC mode) and be a decent option if you can't use dampers on the vents to the first floor, but otherwise, it's one more thing that can break and I'm a fan of keeping things simple. You may also want to see if they have a system that supports two thermostats and electronically controlled dampers which would cut down on some of the extreme temperature swings you likely have upstairs.