Get China Eastern Airlines ( from London Heathrow Terminal 4 in UK ) Non-Stop to Shianghai by Airbus A330 - the route passed over Norway, Sweden, Estonia, Russia & Mongolia thus avoiding getting shot-down over Ukraine !  ( With movies and USB for charging or photos ) then connecting flight to Laos or Cambodia. I went to Phnom Penh from Shianghai. I definitely recommend China Eastern - friendly staff - good ( veggie ) food - clean planes - and they didn't lose my bags ! ( Bags are transfered to the connecting flight for you). The flight to Phnom Penh was only half full and I could use 3 seats and lie down to sleep ( no movies on this small plane ) Free allowance of 2 Bags of 23 Kgs = 46 Kgs plus 5 Kgs carry-on plus laptop = 51 Kgs + laptop - This is in Economy class. One bag was 23.1 Kgs and the other 23.9 Kgs which is OK - I also paid £100 for an extra bag which can be 23 Kgs also. Carry-on was 6.5 Kgs no problems. Very nice free slippers on the Phnom Penh flight. Flight from Heathrow terminal 4 left at 9:20 pm arrived Shianghai 4pm local time - wait in transit lounge until 7:30pm boarding for 8:00pm flight. Arrived Phnom Penh 11:05 local time.
Phnom Penh airport is small but quite modern with no customs checking that I could see. A taxi from the airport to anywhere in the town is supposed to cost $10 - it was night when I arrived and they wanted $12 but the taxi driver said in the daytime IF the traffic is not bad it is $10. However in the daytime the traffic is always bad so I don't know how it can ever be $10.

$12 is OK for a 10 kilo ride in an air-con taxi ( in the daytime it takes an hour ) Actually the traffic is a real nightmare and makes Bangkok traffic look sane. 

Air India , SriLanka Airlines , Bangladesh Biman , or for non-stop flights : Gulf Air , Emirates , Singapore Airlines , KLM , Lufthansa , Garuda , British Airways ... or Thai International ( not recommended )
By bus : ( 3rd November 2015 ) SENGCHALUEAN VIP Bus - direct to Pakse $30.75 Bus leaves at 7:00 am from Sorya Bus Station and reached the border at 4:15pm - roads were OK - only quick stop for lunch near Kratie - 1 hour at border for visa service ( $5 ) then Pakse ( Kilometre 2 ) 7:30 pm - an old Lao bus, but quite OK - plenty of legroom.Book ticket the day before - If you want to break the journey get a ticket to Kratie or Stung Treng and stay overnight . Phnom Penh Sorya Transport seems OK. Paramount Angkor Express is NOT recommended ! Stung Treng Bus departs ( $14.50 ) about 8:00 am and reached Stung Treng 6:00 pm ( Stung Treng is a bit of a hole with not much to do so it is also very possible to stop off at Kratie ) Remember the bus number as they remove the sign with destination in English after the bus departs ( or maybe it falls off ? ) and there can be many buses at the two rest stops and they all look alike . Do NOT stay at Riverside guest house - they must have new management : very unfriendly , price of rooms has increased and they denied there was a morning bus to Pakse although I booked a morning bus with them only a month before . Next door is Sampheap Guest House - a much better deal : $6 double room with en suite , TV (some English channels ) , hot shower , fan , breakfast available .Ticket to Pakse $17 with Rith Mony Transport ( next door ) leaves 9:00 to 9:30   

Buses from the 3 bus stations in Pakse to all parts of Laos and also to Thailand , Cambodia and Vietnam . Tickets can be arranged in Guesthouses and Hotels. To go to Paksong it is most convenient to take a " song taell " ( it means 2 rows and is a small truck with 2 rows of seats ) from Dow Heung Market in Pakse - if you are lucky you can sit in the front - it takes about two and a half hours and costs 20,000 Kip . These song taell also go from the kilometre 8 ( Luk 8 ) Southern Bus Station . Departure times are from 8 am to 12:30 pm and maybe even a bit later.  A song taell goes to Tung Wai once a week from Luk 8 for 40,000 Kip at about 11am.             For bus to Vientiane book the day before at your hotel or guest house . Pick up is at 7pm and the bus leaves at 8pm every day for 170,000 Kip - it is a VIP sleeper bus .                 For daily bus to Phnom Penh book the day before at Pakse Travel Company - 7:15am pick up at your hotel or guest house for 220,000 Kip. 3 hours to Cambodian border - visa on arrival . Pakse travel ( opposite Jasmin ) is open everyday except for festival days or public holidays when everywhere may be closed.  I took  a bus to Kratie for 150,000 Kip - no problems, but the air-con is very cold so bring a jacket.

China Eastern Airlines Departed Heathrow at 9:20 pm arrived Shianghai at 4:00 pm Departed Shianghai at 8:00 pm ( next day ) Arrived Phnom Penh at 11:05 pm. No problems with security check anywhere : did not have to take boots off and no air-blast cubicle for vapour traces like in Bangkok. Homeopathic Remedies were no problem. No check of laptop or cellphones ! Phnom Penh Sorya Transport bus leaves Phnom Penh at 7:30 am for Stung Treng ( $15.50 )  - I decided to break the journey and took the 7:30 air-con bus to Stung Treng. Be at the bus station by 7:00 and get ticket in advance in case the bus is full. Despite warnings on the Internet NOT to ever use this bus company or Paramount Angkor Express, I did not have any trouble and there is not much choice of bus to Stung Treng. ( There is GST Express bus company with ancient buses. ) The problem seems to be with the double-decker buses that are used on the popular routes : the lower deck is for luggage and only the top deck for passengers so staff can pilfer expensive items en route. The less-popular Stung Treng route used a Hyundai single decker bus - luggage in lockers with only outside access – so no problems there. Expect luggage to be covered with a thick layer of reddish-brown ( iron oxide ? ) dust when you arrive ! Staff were friendly and the driver steady and safe. Free bottle of cold water and cold cloth. The first part out of Phnom Penh was on dirt roads , then tarmac roads for the middle part and then bad dirt roads for the last bit. Two stops to stretch your legs at Kompong Cham and Kratie – only the first stop seemed to have toilets available ( no toilet on the bus ) Arrived at Stung Treng 8:50 – a very short walk to Riverside Guest House - See Warning about this place in " Phnom Penh to Pakse " - ( Tuk Tuk if you have luggage ) where a very nice double room with en suite was $8. Air-con is available and fast wifi. Riverside Guest House had a “ Centre-Off “ cold water tap in the bathroom which I have never seen before – I have seen toggle switches with a centre-off position , but can't see why anyone would want to make a cold water tap with this facility – it's not like it was a mixer tap for hot/cold or anything. Be ready at 8:30 for bus to Pakse ( $16 ) The first leg of the journey was by Mercedes minivan ( no air-con ) which left at 9:15 and arrived at the Cambodia/Laos border at 11:00 . Riverside Guest House have their own ticketing service and because the minibus was only half-full I could stretch out across all three back seats . Roads really appalling - full of huge flooded potholes – the tarmac has long gone and I don't think any maintenance has been done since the French left . At the border it took three Cambodian Immigration Officials half an hour to give me an exit stamp and then there is a “ service “ to take your passport 50 meters to the Laos immigration for Laos visa . Visa should cost $42 but I was charged $50 . Then you have to carry your bags ( or pay $2 for a motorbike to assist you with bags ) to the Laos side and take a new minibus . However this minibus stops after 5 minutes and you have to change yet again to a full-size bus to Pakse . The Chinese-built Lao roads are such a change from Cambodian ones – they are like British country B roads and there were even some dual carriageways – something unheard of in Cambodia where it would prevent driving in both directions at once ! The bus made good time to Pakse and arrived about 3:30 pm. Then a small truck ( called a Tuk-Tuk , but it's not really ) to Sabaidy2 Guest House where a quite nice room with mosquito-net and shared bath ( with the bliss of free hot shower ) costs 45,000 kip ( $5.50 ). Wifi wouldn't work earlier but is fast/ish after midnight !