"Shake out" idiomatically means to empty out by shaking. So, if you "shake out your shoes" it means you are shaking them to get unwanted things out of them, for example, if you got small stones or bits of gravel inside your shoe. It would not be idiomatic to say this about the process of getting dirt of the outer part of a shoe.
"Dust off" idiomatically means to brush the dust off something, typically the exterior. So dusting off shoes might involve brushing the outer part of the shoe.
These are therefore two different processes. You could say "dust off and shake out my shoes" if you want to indicate both, or just say "clean my shoes inside and out".