* Convoy had entered Ukraine without government's permission
* Western states demanded withdrawal of "illegal" convoy
* NATO, White House say Russian artillery used inside Ukraine
* Germany's Merkel due in Kiev later on Saturday
* Shelling destroys homes in rebel-held city of Donetsk (Updates, adds background, shelling )
By Dmitry Madorsky
DONETSK-IZVARINO BORDER CROSSING, Russia, Aug 23 (Reuters) - T he first trucks from a Russian aid convoy started crossing back into Russia on Saturday after igniting a storm of anger in Western capitals a day earlier by driving into Ukraine without the permission of the government in Kiev.
The return of the trucks may help ease the tension to some extent in time for the arrival of Germany's Chancellor Angela Merkel in the Ukrainian capital later on Saturday for talks on how to end the crisis over Ukraine.
Western leaders had joined Kiev in calling the Russian convoy -- about 220 white-painted trucks loaded with tinned food and bottle water -- an illegal incursion onto Ukraine's soil, and demanded that they be withdrawn as soon as possible.
A Reuters journalist at the Donetsk-Izvarino border crossing, where the convoy rolled into Ukraine on Friday, said about 10 trucks had passed back into Russia and more could be seen in the distance arriving at the crossing.
Russian state television had earlier broadcast footage of some of the trucks being unloaded at a distribution depot in the city of Luhansk, eastern Ukraine.
The city is held by separatist rebels who are encircled by Ukrainian government forces, and has been cut off from power and water supplies for weeks. International aid agencies have warned of a humanitarian crisis.
NATO said it had evidence that Russian troops had been firing artillery at Kiev's forces inside Ukraine - fuelling Western allegations that the Kremlin is behind the conflict in an effort undermine the Western-leaning leadership in Kiev.
The White House made the same allegation. "We have seen the use of Russian artillery in Ukraine in the past days," said U.S. deputy national security advisor Ben Rhodes.
Russia denies giving any material help to the rebellion in eastern Ukraine, a mainly Russian-speaking region. It accuses Kiev, with the backing of the West, of waging a war against innocent civilians.
The conflict in Ukraine has dragged Russian-Western relations to their lowest ebb since the Cold War and sparked a round of trade sanctions that are hurting already-fragile economies in European and Russia.
The crisis over Ukraine started when mass protests in Kiev ousted a president who was close to Moscow, and instead installed leaders viewed with suspicion by the Kremlin.
Soon after that, Russia annexed the Ukrainian region of Crimea, and a separatist rebellion broke out in eastern Ukraine. In the past weeks, the momentum has shifted towards Ukraine's forces, who have been pushing back the rebels.
The separatist are now encircled in their two strongholds, Luhansk and the nearby city of Donetsk.
Heavy shelling could be heard early on Saturday in Donetsk, a Reuters reporter in the city said.
A printing plant in the southern part of the city was hit around 6:00 a.m. (0300 GMT) and three hours later flames and black smoke could still be seen.
A residential area in Donetsk's Leninsky district was also hit by shelling. Reuters reporters saw shell craters and several heavily damaged single-storey buildings.
A man who gave his name as Grigory, said he was in the toilet when he heard the whistling sound of incoming artillery. "Then it hit. I came out and half the building was gone."
The roof of the building had collapsed into a heap of debris. Grigory said his 27-year-old daughter was taken to hospital with injuries to her head. He picked up a picture of a baby from the rubble. "This is my grand son," he said. (Additional reporting by Maria Tsvetkova in Donetsk, Ukraine; Writing by Christian Lowe; Editing by)