Most efficient way of making pair list from a list

About 4x faster:

Partition[Flatten @ data[[All, {1, 2, 1, 3, 1, 4, 1, 5}]], 2]

I think you'll find this faster:

pairem[data_] := 
 Module[{c = ConstantArray[0, 8*(Length@data)], 
   p = Flatten@data[[All, 2 ;;]], p2 = data[[All, 1]]},
  c[[2 ;; ;; 2]] = p;
  c[[1 ;; ;; 2]] = Flatten@Transpose[ConstantArray[p2, 4]];
  Partition[c, 2]]

Edit: this method is optimized for long sublists which is exactly the opposite of your example. Sorry. I'll post if I find anything applicable.

---

This is fairly clean and on larger data at least as fast as rasher's code:

fn = ArrayFlatten[{{First@#, Rest@# ~Partition~ 1 }}] &;

Test:

fn /@ {{3, 7, 1, 6, 5}, {8, 2, 4, 1, 2}, {8, 1, 5, 2, 5}}

{{{3, 7}, {3, 1}, {3, 6}, {3, 5}},
 {{8, 2}, {8, 4}, {8, 1}, {8, 2}},
 {{8, 1}, {8, 5}, {8, 2}, {8, 5}}}

x = RandomInteger[99, {5000, 5000}];

fn /@ x   // AbsoluteTiming // First
pairem[x] // AbsoluteTiming // First

0.334019

0.383022

A related question: Prepend 0 to sublists