Seeing as Conkeldurr is a very slow Pokemon increasing it's speed would be redundant when compared to your other options.
Special Defense is an option, but probably not a good one. If you EV train then doing a little bit of EV training in Special Defense is a good idea.
I would say the best nature you can get is Adamant, as it increases Conkeldurr's most prominant stat giving it a nice buff to gain some extra damage.
Adamant is the way to go.