If you want to animate the folding process, shape keys might work; I think the armature approach might be better because each shape key transitions to another in a straight line. For instance, when folding the “paper” diagonally, with a shape key for the start and end position, one corner would just slide to the other rather than rotating around the fold line.
To make it “fold” correctly, you would need to add a lot of shape keys in between the beginning and ending shape key - more keys would provide smoother movement (be sure to set the interpolation to linear rather than the default bezier for the in-betweens at least).
For an armature approach, I would consider creating “hooks” for each vertex, and use an armature to animate the hooks. To create a hook, select a vertex, and press CTRL-H:Hook To New Object. This will create a new empty which the vertex is now parented to.
Whichever way you go, it will take a lot of planning to make sure you have vertices in the right places and to keep your armature from becoming too complicated. Also, you might want to make the empties different from each other (use plain axes, axes with arrows, a cube, sphere, etc.). this would make it easier to tell which vertex you are dealing with when they overlap - for instance, the first diagonal fold puts two vertices in the same place.
Lastly, using just a plane may not be best since both sides of the “paper” would have the same material. Perhaps a very, very thin box?
This is an interesting puzzle, and I will probably spend the next couple days trying to figure it out. Thanks for the inspiration!