It's really hard to give suggestions without knowing what DF's current pathfinding code is doing. A few observations though.
* Too much work is being done finding really long paths. No matter how much work you do to speed up pathfinding, a really long path is always going to be more work. Moving to the wrong side of a block to mine, going to the staircase to get a stone 1 z-level down rather than one 3 tiles away on the same level ... those things eat up CPU.
* Too many things are using pathfinding. Why are animals using the pathfinding code? A routine that tries to move towards something the animal sees and gives up if it's blocked is not only faster, it's usually more realistic. (Make an exception for trained animals.)
* Some variant of the A* algorithm is probably best, but A* reacts badly to situations that are natural in multi-Z-level pathfinding, things like this:
########################################
#......................................*
#.######################################
#..@....................................
########################################
* Setting the default pathing cost at higher than 1 kills the performance of A* when the best path is close to a straight line. Seriously. But due to the multi-Z-level problem you probably won't notice.
* Nobody cares if your pathfinding gets the absolute shortest path, as long as it's not dramatically wrong.
* A* can be modified to find a path to the closest one of many things. This is often faster than first choosing an item then pathing to it.