How to effectively clean existing bricked columns?
It doesn't look like concrete splatter to me, just rough mortar from laying the bricks, way back when. This means there is nothing to 'clean off' if you like, rather the protruding mortar needs scraping back and it looks to be a fairly strong mortar. 

I'd use a flat, cold chisel held at a shallow angle and a light-ish hammer (2lb or 1kg) and gently chisel or chip away the excess mortar. Much like a stone mason, carving a statue if that description helps. 

Obviously stop once you are close to the bricks. Then I'd fill in any gaps, or damage with new mortar before painting. NOTE: When you fill in any gaps, think more like re-pointing the joints rather than filling a hole in drywall. Then the brickwork will look better once painted. If you smear the mortar all over the hole, this will look worse/obvious once painted.

Bear in mind this column was not built as 'face work', i.e. it is supposed to be covered up.Thus you are looking at some work to make it 'pretty'.