What are the best connections by bus ?
Also, is it safe to cross the border, or am I might going to have some troubles especially traveling by bus in the night ?
By bus, the easiest is going to be a stop in La Paz, Bolivia.
You have two options from Puno. The direct - through the border and round the south side of Lake Titicaca to La Paz. It doesn't take that long - about 5 hours from memory, although I've heard it can take 8.
Option B is the ferry through to Copacobana. It's meant to be quite the experience, but takes longer. You'll also likely have to change buses in Copacobana, so be prepared to lose your good seats, if you have any.
From La Paz, it's 12-15 hours by bus to the town of Uyuni. Be aware - it can be FREEZING at night on the bus, especially during winter. Pack warm. I was in a car for various reasons, was given a blanket, wasn't sure why until a few minutes into the drive - was very thankful for it!
Some routes are direct from La Paz, others will go through Oruro, and you'll need to change buses there.
In terms of the border, it was one of the more fun ones that I remember. Don't worry about it being open - the bus from Puno won't leave if it's not. In terms of safety, it was a little confusing but just follow everyone else on the bus and someone will wave you into a queue, a room, and so on. And make sure you know what your bus looks like - the driver may well move it down to the other side of the border without you realising :)