There is a hint in the differences by looking at the different characters used: 数 vs 間.
数 indicates that numbers are involved, as seen in the definition of 手数 → 動作・作業の数. In other words, the number of steps or amount of work necessary is the focus.
間 indicates that time is involved, as seen in the definition of 手間 → 費やされる時間や労力.
In other words, the amount of time and the amount of effort is the focus.
So, let's look at some examples:
I think both of the above phrases could be used, but the focus is different. The first implies a dish which takes a lot of time and effort to make, while the second one implies a dish which requires a lot steps to make.
XXのネットサービスを利用すれば、お店まで行く手間が省ける (If you use XX internet service, you don't have to go all the way to the store)
In the above sentence, since we are talking about effort, I think 手間 is more suited than 手数 because we are not talking about something that involves multiple steps, etc. we are talking about the effort of going to the store.
There is another different between the two:
You might see the above often as a fixed expression. However, we cannot use 手間 here. Why? Because 手数をかける is always directed toward somebody else and implies somebody else will do something for you (as noted in your second definition), whereas 手間をかける will imply something that you do yourself, such as 手間をかけて作ったケーキ (a cake that you put time and effort into to make).
Also, 手間 often has a strong emphasis on time, like in the following sentence: