Take bus no.10 ("9. maj") from the central square (the bus stop is next to McDonalds). Get off at the last stop, in a suburban area called Novo Selo (also referenced as "Naselje 9. maj"). The bus ride should cost around 50 RSD. Walk straight on in the same direction and cross a bridge over the motorway. You will come to a roundabout, and the left path leads to the motorway, heading south. You can hitch from here. The E80 and E75 split shortly afterwards, so make sure you're going in the right direction. For [[Skopje]], Leskovac is on the way, so you can accept a ride to that vicinity.
(I did not find a roundabout, but highway was easy to approach from the bridge and parking spot is like 50 metres far. - Solop, Dec 2016)
Another possibility is to take the train towards Doljevac from the main railway station. Get out at Doljevac station (10 -15 minutes ride, ticket price 64 RSD, about 30 RSD if you manage to bribe the conductor), and take a 10 minutes walk to the motorway toll station (accros the fields).