What you are saying is you would like to compare the paired t-test statistic to the distribution of such statistics obtained by independently switching all possible pairs of data. There are $2^{10}=1024$ such switches, small enough to enable fast computation of the full distribution.
It is convenient in R to code this as a t-test for the difference between the two sets of data: instead of switching values, we merely need to negate them.
Let's first run the t-test:
x <- c(12.9, 13.5, 12.8, 15.6, 17.2, 19.2, 12.6, 15.3, 14.4, 11.3)
y <- c(12.7, 13.6, 12.0, 15.2, 16.8, 20.0, 12.0, 15.9, 16.0, 11.1)
(value <- t.test(x,y, paired=TRUE, alternative="two.sided"))
The statistic and p-value are $-0.213$ and $0.836$, as expected. Now let's generate the permutation distribution (using expand.grid as requested):
perms <- do.call(expand.grid, lapply(as.list(1:length(x)), function(i) c(-1,1)))
dist <- apply(perms, 1, function(p) t.test(p*(x-y), alt="t")$statistic)
(This takes $0.33$ seconds.) As a quick check, let's graph the results:
hist(dist)
abline(v = value$statistic, col="Red", lwd=2)

Because the actual statistic is near the middle of the distribution and this is a two-sided test, the p-value looks approximately to be $0.9$ or so. We can compute it:
sum(abs(dist) > abs(value$statistic)) / 2^length(x)
The result is $0.836$, the same as the t-distribution gave us.
Also just to add, I thought the permutations where 2^20, which did indeed take a while.
Many thanks
– user1453477 Nov 19 '12 at 20:01sum(abs(dist) >= abs(value$statistic)) / 2^length(x), giving a p-value of 0.8710938? – caracal Nov 19 '12 at 22:56Thanks.
– user1453477 Nov 26 '12 at 19:47