No, you can't use an intercept of zero. It's not clear what that would mean for this test. As the wikipedia page describes, this test computes the slope for all pairs of points and then reports the median of those slopes. If you know you want the fitted line to start at zero, this doesn't quite make sense. Maybe you'd want to compute the slopes of all points compared with that zero point only, but that wouldn't be the Theil-Sen estimate anymore; it would just be the sign test.
And no, you can't use a matrix on the right side; this test is for one predictor only. The slope between two pairs of points then has both a magnitude and a direction, and it's not clear how one would take the median of them.
Finally, the default for this function is to use Siegel repeated medians; for the Thiel-Sen test, you need to specify repeated=FALSE. See the help page for more information.
The Theil-Sen estimator is essentially an estimator for the slope alone; the line has been constructed in a host of different ways - there are a large variety of ways to calculate the intercept.
You said:
My understanding of the intercept calculation is that I first calculate the median slope, and then construct a line through every data point with this slope, find the intercept of every line, and then take the median intercept.
A common one (probably the most common) is to compute median($y-bx$). This is what Sen looked at, for example; if I understand your intercept definition correctly this is the same as the intercept you mention.
There are a couple of approaches that compute the intercept of the line through each pair of points and attempts to get some kind of weighted-median but based off that (putting more weight on the points further apart in x-space).
Another is to try to get an estimator with higher efficiency at the normal (akin to that of the slope estimator in typical situations) and similar breakdown point to the slope estimate (there's probably little point in having better breakdown at the expense of efficiency), such as using the Hodges-Lehmann estimator (median of pairwise averages) on $y-bx$. This has a kind of symmetry in the way the slopes and intercepts are defined ... and generally gives something very close to the LS line when the normal assumptions nearly hold, whereas the Sen-intercept can be - relatively speaking - quite different.
Some people just compute the mean residual.
There are still other suggestions that have been looked at. There's really no 'one' intercept to go with the slope estimate.
Dietz lists several possibilities, possibly even including all the ones I mentioned, but that's by no means exhaustive.
Best Answer
Wikipedia points to no less than six papers detailing different deterministic or randomized algorithms with $O(n\log n)$ performance, right in the section where they mention the existence of such algorithms (as well as mentioning an even faster one under particular circumstances).
Deterministic:
Cole, Richard; Salowe, Jeffrey S.; Steiger, W. L.; Szemerédi, Endre (1989), An optimal-time algorithm for slope selection, SIAM Journal on Computing 18 (4): 792–810, doi:10.1137/0218055, MR 1004799.
Katz, Matthew J.; Sharir, Micha (1993), Optimal slope selection via expanders, Information Processing Letters 47 (3): 115–122, doi:10.1016/0020-0190(93)90234-Z, MR 1237287.
Brönnimann, Hervé; Chazelle, Bernard (1998), Optimal slope selection via cuttings, Computational Geometry Theory and Applications 10 (1): 23–29, doi:10.1016/S0925-7721(97)00025-4, MR 1614381.
$\ $
Randomized:
Dillencourt, Michael B.; Mount, David M.; Netanyahu, Nathan S. (1992), A randomized algorithm for slope selection, International Journal of Computational Geometry & Applications 2 (1): 1–27, doi:10.1142/S0218195992000020, MR 1159839.
Matoušek, Jiří (1991), Randomized optimal algorithm for slope selection, Information Processing Letters 39 (4): 183–187, doi:10.1016/0020-0190(91)90177-J, MR 1130747.
Blunck, Henrik; Vahrenhold, Jan (2006), "In-place randomized slope selection", International Symposium on Algorithms and Complexity, Lecture Notes in Computer Science 3998, Berlin: Springer-Verlag, pp. 30–41, doi:10.1007/11758471_6, MR 2263136.
Which did you want?