I think of these as policy objects, and they only make sense when you have choices. That is, the benefit is not from pushing the logic into a new class. The benefit is from removing a switch on a policy flag, and using the runtime dispatching that the language provides. That is, instead of writing the branches yourself and keeping the current policy as a flag, class names are your policy flag and virtual methods are your branches. It pushes low-level code (if state A, do this, if state B, do this...) into the language runtime.
Personally, I don't make policy objects until I have two options. If I have one option, I hardcode everything because I want to do the minimal amount of design necessary. I only add in the abstractions when they're necessary.
In his post, this benefit was mostly an aside - "and have them be different" while showing one other option. Pushing logic into classes is not desirable in itself. As you pointed out, it adds layers of abstraction onto what can be conceptually simple tasks. But when you're able to remove some of your own machinery and rely on existing machinery, it's a win.
Although I do most of my work in C++, and I often have to create function objects - C++ has free functions, but it's often easier to pass around function objects. In his examples, I think PostCategorizationPolicy and UserCategorizationPolicy would be better served as functions.