Hi there, a couple of thoughts for you.
1. The way the software is integrated, you would only be able to void an order that is in Authorized state, or not Captured in admin. Check that your order is not already captured. If captured, you'd have to do a refund, not a void. This may work for you because it would create a new tax document.
2. The response from Avalara means that it cannot find a tax document that matches your order number. Is it possible that this order was created prior to turning on Avalara? In that case, there'd be no matching document at Avalara to void.
Hope these suggestions help.