HASKELL 111 (211-100 bonus)
It seems to me that a few answer miss a point: using at most k n. This means that f(4,3) can generate (4/4) = 1 or (4*4)=16.
Anyway that's my answer. I assume int/int to behave as floor. Exponentiation is included.
import Data.List f=[(+),(-),div,(*),(^)] c=concatMap a y f=f y o n x=map(a n.a x)$f++map flip f l 1 _ s=0:s l k o s=c(l(k-1)o.filter(>0))[c o s,s] t[n,k]=l k(o n)[n] main=interact$show.sort.nub.t.map read.words 