A few years ago I covered my backyard garden with a thick layer of newspapers to kill the weeds. Now I think I might have spoiled the soil and have to do something to change its quality. What should I do now?
Covering soil with plastic or newspapers is a common way of killing weeds in soil. You haven't ruined your soil in any way. Just do whatever you were planning.
I would till the soil as little as possible. The proper way to do this is to prepare the soil for planting before covering like this. A lot of people cover their soil, kill the weeds and then till the soil which brings lot of dormant weed seeds to the surface. Then they sprout and you conclude the process was a waste of time when it wasn't.
You won't have 'spoiled' the soil - newspaper is biodegradable, lets air and water through, so the soil beneath won't be sterile and without life. Whether you improve what's there by adding humus rich materials (composted animal manures, leaf mould, garden compost you've made yourself, anything like that) is largely dependent on what you actually want to grow in the ground. Some plants don't appreciate manures (root vegetables) but plenty of others do. Raising the humus content of the soil, though, is never a bad thing to do; by and large, most plants will thrive in amended soil because it improves bio diversity, thereby improving growing conditions.
Now that the weeds are dead the best thing to do is dig up the roots of the weeds and bang out all excess soil then through them away ( I would not compose them because once most weeds get water their roots create more plants). Water the yard when necessary to loosen up the ground for grass to grow in. The process of grooming the yard may take weeks depending on the size but is worth it.