See "On the number of primes $p$ for which $p+a$ has a large prime factor." (Goldfeld, Mathematika 16 1969 23--27.) Using Bombieri-Vinogradov he proves, for a fixed integer $a$, that
$$\sum_{p \leq x} \sum_{\substack{ x^{1/2}< q \leq x \\ q | p+a}} \ln q = \frac{x}{2} + O\left(\frac{x \ln \ln x}{ \ln x} \right)$$
where the summation is over $p$ and $q$ prime. Note that this implies that the number of primes $p$ less than $x$ such that $p-1$ has a prime factor greater than $p^{1/2}$ is asymptotically at least $\frac{x}{2\ln x}$.
Let $A_n = \{a : a \equiv 1 \mod 2^n \mbox{ and } 2^{2^{n-1}} \leq a < 2^{2^{n}} - 2^{2^{n-1}}\}$, and let $\displaystyle A = \bigcup_{n=1}^\infty A_n$.
Then, $A(x) >> \frac{x}{\log x}$, the gap sizes are $<< \sqrt{x}$, and $A$ contains infinitely many non-multiples of $m$ for every $m>1$.
However, $2^{2^n}$ cannot be written as a sum of fewer than $n-\log_2 n$ elements of $A$. To prove this, suppose the contrary; say $2^{2^{n}} = a_1 + \cdots + a_k$ for $k < n-\log_2 n$, $a_1 \leq \cdots \leq a_k$, $a_i \in A$. We know that $a_k \in A_n$, because if not, then all the $a_i < 2^{2^{n-1}}$, so, summing, $2^{2^n} < k \cdot 2^{2^{n-1}}$, implying $2^{2^{n-1}} < n$, which is false for positive $n$. One applies a similar argument to each of the partial sums of the $a_i$, in turn from largest to smallest, to show that $\displaystyle a_j \in \bigcup_{i=n-k+j}^n A_i$. In particular, each $a_j \equiv 1 \mod 2^{n-k+1}$, so the sum $2^{2^n} \equiv k \mod 2^{n-k+1}$. Thus, $2^{n-k+1} \mid k$; in particular, $2^{n-k+1} \leq k$. Using the bound $k < n-\log_2 n$ on both sides, we may deduce $2n < n-\log_2 n$, a contradiction.
For a possible fix, I would assume that $A$ is well-distributed modulo $m$ (for every $m$) in an appropriate sense. (I'm being purposefully vague here, and you might need something rather strong, like an analogue of Bombieri-Vinogradov). Good luck!
Best Answer
Assuming the Hardy-Littlewood prime tuples conjecture, any n which is coprime to k will have infinitely many representations of the form q-kp.
Assuming the Elliot-Halberstam conjecture, the work of Goldston-Pintz-Yildirim on prime gaps (which, among other things, shows infinitely many solutions to 0 < q-p <= 16) should also imply the existence of some n with infinitely many representations of the form q-kp for each k (and with a reasonable upper bound on n). [UPDATE, much later: Now that I understand the Goldston-Pintz-Yildirim argument much better, I retract this claim; the GPY argument (combined with the more recent methods of Zhang) would be able to produce infinitely many $m$ such that at least two of $m + h_i$ and $km + h'_i$ are prime for some suitably admissible $h_i$ and $h'_i$, but this does not quite show that $q-kp$ is bounded for infinitely many $p,q$, because the two primes produced by GPY could both be of the form $m+h_i$ or both of the form $km+h'_i$. So it is actually quite an interesting open question as to whether some modification of the GPY+Zhang methods could give a result of this form.]
Unconditionally, I doubt one can say very much with current technology. For any N, one can use the circle method to show that almost all numbers of size o(N) coprime to k have roughly the expected number of representations of the form q-kp with q,p = O(N). However we cannot yet rule out the (very unlikely) possibility that as N increases, the small set of exceptional integers with no representations covers all the small numbers, and eventually grows to encompass all numbers as N goes to infinity.