You are probably right, the reason those pavers 'sunk' was because of a poorly made paver bed. Just take those pavers up...store them, they are worth putting somewhere else or making paths out of them. I would get rid of all growing stuff, regrade so that that entire area has at the very least 2% grade AWAY from your foundation. How high is the back of your yard in relation to your foundation? You might have to make a swale to capture excess water and allow to reenter the soil and water table. Be careful where this swale directs excess water. Anywhere off of your property could make lots of trouble. There is also the solution of making 'dry wells' to collect excess water yet still allow lawn to grow above. NO sand at all is indicated! Just slope that surface away from your foundation! Good call btw. Talk about reducing the value of your home!
I would replace with sod. Remove only soil to get water flowing away from your foundation. That soil can easily be thrown on top of plant beds or used to beef up or make new plant beds. No soil whatsoever should be brought in. Cut equals fill...is a big time rule. A swale is a gently sloping 'ditch'...if the property behind your home is higher than your foundation. Provide more information, there are also solutions to include trench drains and the like but you have to remove those pavers and soil until every drop of water that lands near your foundation is directed away from your foundation. Please send a picture because I am assuming an awful lot.