Python 3 (imperfect), 449 - 300 = 149

Suffers from all the same shortcomings as KSab's solution: no unary operators, fully parenthesized, contains equivalent expressions like (1+1)+1 and 1+(1+1). I eliminated exact duplicates by passing the results to set(). The output could be a bit uglier to save a few bytes, but I like it this way. I also didn't do nth roots because it doesn't seem like they buy you much in this problem.

R=range E=lambda z:eval(z.replace("^","**")) def m(d,n):_=R(1,11);s={i:[]for i in _};r=R(1,n);n<2 and s[d].append(str(d));d=str(d);t=[[(d*i,i)for i in r]]+[[]]*n;h=[];[(h.append("("+A+o+B+")"),t[l].append((h[0],a+b))if a+b<n else E(*h)in _ and s[E(*h)].append(h[0]),h.pop())for l in r for j in R(l)for A,a in t[j]for k in R(l)for B,b in t[k]if a+b<=n for o in"+-*/^"if(o=="^"and-~-(0<E(B)<9)or 0==E(B)and"/"==o)-1];[print(i,set(s[i])or'')for i in _] 

This will take several minutes to run if the second argument is 5. Test by calling m(digit, number):

>>> m(1,3) 1 {'((1*1)^1)', '(1^(1+1))', '((1-1)+1)', '((1/1)/1)', '((1*1)*1)', '((1^1)/1)', '(1*(1*1))', '(1^(1*1))', '(1+(1-1))', '(1^(1^1))', '((1^1)*1)', '(1^(1/1))', '((1/1)*1)', '(1-(1-1))', '(1/(1^1))', '(1/(1*1))', '(1/(1/1))', '(1*(1^1))', '((1+1)-1)', '((1*1)/1)', '((1^1)^1)', '(1*(1/1))', '((1/1)^1)'} 2 {'(1*(1+1))', '((1^1)+1)', '((1+1)/1)', '((1*1)+1)', '((1+1)^1)', '(1+(1*1))', '((1/1)+1)', '(1+(1^1))', '(1+(1/1))', '((1+1)*1)'} 3 {'((1+1)+1)', '(1+(1+1))'} 4 5 6 7 8 9 10 {'(11-1)'} >>> m(3,3) 1 {'((3/3)^3)'} 2 {'(3-(3/3))', '((3+3)/3)'} 3 {'(3-(3-3))', '((3-3)+3)', '((3/3)*3)', '(3*(3/3))', '(3/(3/3))', '((3+3)-3)', '(3^(3/3))', '(3+(3-3))', '((3*3)/3)'} 4 {'((3/3)+3)', '(3+(3/3))'} 5 6 {'((3*3)-3)'} 7 8 9 {'(3+(3+3))', '((3+3)+3)', '((3^3)/3)'} 10