Recent experience with Senegal -> Mali border crossing
I just did this crossing at Moussala (past Niokolo-Kobo national park) and thought I would write down my experience for those that follow.
This was a no-hassle crossing, the people were friendly and one gendamarie even got on his bike to guide me to where the customs post was... all in all I recommend it. The only problem is that on the Mali side things are very much not clear on what you need to do, and the places you need to go are scattered around town.
On the Senegal side, you need to stop and go into the border police station at Kedougou. I don't think they stamp anything but the officer was nice and gave me directions on how to proceed. Then you drive to the Douane (customs) office in Seraya. I had a carnet and the process of getting stamped out was quick and easy... although I didn't understand at first that this was the customs post for the border and had a 50km drive back to get the carnet stamp! The stop is obvious from the road but the building itself is down the side road a bit. Then at Moussala you have the final visa stamp out and on to Mali.
Over the bridge there is a stop where you need to go get a stamp from the border police. Then drive on to Kenieba for everything else. Before Kenieba there is another check, and I think this is where you should get the visa, but I didn't realize that and went on to Kenieba. After entering Kenieba there is a dirt road going off to the right, if you pass a gas station on the right you've gone too far! A few hundred meters down this road you will find the Douane building, then another few hundred meters to the Gendamarie, then a bit further (with a left and a right) to get to the police station where I got my visa. It was at the police station where they seemed confused, so I might have done a few things wrong... I'm not sure. My french isn't 100% so it was hard for me to follow what they were telling me sometimes.
Kenieba Douane: N12 51.447 W11 14.341
Kenieba Gendamarie: N12 50.871 W11 14.176
Kenieba Police: N12 50.705 W11 14.036
The visa cost me 15K CFA (about 22 euros), and everybody was friendly.
All the roads except to the offices in Kenieba all the way from Kedougou to Kita is paved, although at some points there is more pothole than road. Most of the road is in decent shape.
I have put the route (a lot of which was wrong or missing) into OpenStreetMaps as well as POI for the checks.
My Michelin map of Africa and GPS shows no road connecting Kenieba to Bafing, but it's a nice new paved road.
Edit: forgot these details. I had a 15 year old Land Rover with a carnet, a british passport, and no visa.