What you are asking about is known as the universality problem. In the slides by Jeffrey Shallit (http://www.cs.uwaterloo.ca/~shallit/Talks/open10r.pdf, slide 36) it is mentioned that this problem is PSPACE-complete for NFA. So it is highly unlikely that a polynomial algorithm exists for it. Please, let me know if you need an exact reference to the proof of the PSPACE-completeness (see edit2).
edit. I forgot to mention that because the universality problem for DFA is simply solved in polynomial time the existence of a poly(n, d) algorithm in your second question also implies PSPACE=P and is very unlikely.
edit2. The proof of PSPACE-completeness can be found in the lecture notes here: http://www.wisdom.weizmann.ac.il/~vardi/av/notes/ (the proof itself is in lecture 4).
