You could say that pathing from a to b without a road takes 20% more effort. So maybe the dwarf gets a bit more tired by having to use some extra energy to go through it, but not enough to make a difference, since they just don't go around running at full speed everywhere and its such a short distance.
I'm confused why you think that running = fixed effort, but you think walking = fixed speed? It seems much more likely that BOTH are fixed effort: walking is usually at the local max efficiency point for that terrain, and running is at the maximum physical fitness allowance for your body.
And even if you COULD physically possibly walk across scrubland as quickly as pavement, that doesn't mean you will, because you'd have to adopt a weird, less-than-locally-efficient gait for one of those two surfaces for your speed to remain fixed, which would be wasteful. When expending equal effort, you'll walk more slowly on the scrubland, because you have to spend more energy watching for bumps and moving more steadily and lifting your feet a bit higher to clear uneven obstacles, etc.
The pathfinding algorithm would have to be updated to take terrain into account, which could slow things down a bit.
I don't think so. Pathfinding uses a map of costs already. Adding terrain adjustments would be a one time very small delay (like probably 1/3 of a second) when you first make your map, and then would just be there and be as fast as normal, since it's still looking up costs like before. As you change the terrain, there'd also be a brief microsecond to adjust to that new road right as it's built, but imperceptible.