Maybe this is pashut?
Ravina Hava Yasiv Kameih d'Rav Ashi. Chazieh d'Hahu Gavra d'Ka Asar Leih l'Chamreih b'Tzinsa dShabsa.
Rashi
b'Tzinsa- Dekel, v'Ein Mishtamshin b'Ilan Mishum Shvus.
Why is there only a concern about the use of the tree? What about the fact that he was handling the behama? Or that he was tying it? (kesher, etc)
Yehoshua, Yerushalayim, Eretz Yisael
The prohibition against using a tree is because one might come to detach part of the tree, which is Tolesh. The same reason is given for the prohibition against riding an animal; one might come to pull a twig off a tree while riding. However, there is a leniency regarding using an animal, since one may do actions for the animal's benefit.
In this case the animal may require protection, and this is why it was tied to a tree. However, one cannot use a tree for that; one must find other ways to protect it, and this is why Rashi emphasized the prohibition of the tree. (One could also surmise that the date-tree fiber was long and was already attached to the animal's halter so that the only prohibition would be using the tree.)
Regarding tying the animal, there are a number of permitted ways of tying so that this would not necessarily have been the issue here.
Yoel Domb