As most of the time, Seat 61 is the place to start your research. And indeed, the page on the silk road contains lots of useful information on the train from Alma-Ata to Urumqi:
How to buy tickets: You can book these trains in either direction using the Real Russia online system below or (for eastbound journeys) through a local agency such as www.tourasia.kz.
On Real Russia you can select Alma-Ata to Urumqi and a date (you might have to try different options since the train doesn't run daily) and get more information about the train. You should leave GPB as the currency as it will just display 0 as the price in other currencies (at least this just happened to me when I selected €).
There is a stop right before the border (Druzhba) which you can also select using the advanced search (you have to first select the country so that it will suggest the correct Druzhba for you). (Even when selecting GBP the system shows me a price of 0 which obviously can't be correct. I don't know whether your booking request will go through but it certainly is worth a try. (This doesn't happen when I select Alma-Ata as the start, so maybe other cities along the route also work.)) Of course you should check whether you can return your rental car there.
More information about this online booking system can be found at Seat 61.
Your other option (as stated in the above quote) is to get in touch with some travel agency which will get your tickets for some fee.