Eddie is right. I´ve eaten in that restaurant, but it´s far from downtown Madrid. In fact, the best place to eat paella is "La Paella Real" in front ot "El Teatro REal" in Plaza de la Opera.
But yes, at almost any restaurant you can eat an acceptable paella on Thursdays. That will cost you around 8-10 euros with the drinks and the coffe. At "La Paella REal" you can eat different styles of paella, including black calamary rice.