What if you let all threads read the same sp_mat_element[] in a burst read and then let the threads operate on the dense matrix row in parallel? I think that this would solve the problems with shared memory.

Outline of a kernel for many columns in the dense matrix:
- Assign each work group to one row in the result matrix
- Each thread starts with a private float for summing the result entry r.
- Load sp_mat_col_indices and sp_mat_elements into thread-private entries j and x (this is a fast burst-read)
- Fetch the respective row j from the dense matrix into a thread-private entry y
- multiply and add: r += x * y
- Continue with all nonzeros of that row in the sparse matrix.
- Write r to the result matrix

This should not need any shared memory at all and give reasonably good performance as long as there are at least ~32 columns in the dense matrix.