$U = \{ \langle M, x, \#^{t} \rangle \vert M $ is a NTM that accepts $x$ within $t$ steps on some branch$\}$ is NP complete
Finding the running time of a given Turing machine is undecidable. Luckily, you don't need to find the actual degree. You only need to show the existence of a reduction from $A$ to your language, not to construct a procedure that given a description of $A\in\mathsf{NP}$ (say, as the encoding of its verifier), will output a reduction from $A$ to your language.

Think of it this way, let $\{f_n\}_{n\in\mathbb{N}}$ be a sequence of functions, where $f_i(x)=\left(M_A,x,\#^{|x|^i}\right)$. One of the functions in this sequence is the reduction you're looking for, and I don't need to point out which one (note that I can specify it in terms of the degree of the polynomial in the running time of $M_A$).