I would have never even imagined smoked paprika would be the culprit. I mean why add it in the first place? I guess I couldn't get my mind outside of a paradigmatic version of the dish which would already have a certain smoky, nutty aromatic quality to it.
I think the reason for adding it in the first place is because this dish is being prepared in a restaurant kitchen where a wood fire is an absolute impossibility.
I'm not sure whether they're toasting the saffron or not but I think the suggestion of ordering it with regular rather than smoked paprika is a good one. That will surely answer the question. I'll also ask for a towel or cloth napkin to cover the dish and let it sit for 5 - 10 minutes after they serve it. They brought it straight to the table from the oven and some of the liquid had not yet been absorbed.
I also just discovered that another local restaurant, whose menu has always been upscale Italian bistro oriented, now has a chef who grew up in Spain and learned his craft there. He's convinced the owner to add a number of Spanish dishes ot the menu, paella being among them.
I think it's time for a show-down