As the wikipedia article https://en.wikipedia.org/wiki/Death_of_Wei_Zexi makes clear, those medical adverts were not fake. They were certainly deadly. They were also run by the Second Hospital of the Beijing Armed Police Corps. A state owned hospital. On what basis would google refuse to run that ad? Barring them from advertising seems like a great way to get a midnight knock at your door from the Beijing Armed Police Corp. And it's not like an algorithm will easily tell when medical claims are is truthful.
Would the auction algorithm produced a different ad result? Google's pay per click model maximizes revenue per ad shown, not human welfare; presumably the hospital willing to pay to get to the top of the searches is willing to go the extra mile to improve click thru rates.
Would marking it more clearly as an ad have made a difference? Google is already walking down that slippery slope; today Google places ads directly in line with search results. If Baidu is able to legally get away without even marking ads, it seems like Google is an A/B test away from a very profitable locale specific change to the UI.