Just road those roads about a week ago. From Arica, Chile to La Paz is paved the whole way. You go up to about 16,000 feet and the border crossing is simple, just make sure you take plenty of gas.
From La Paz to Puno, Peru via the Yunguyo crossing is all well paved with a wide boarded ferry across Lake Titicaca. Watch the Peruvian police at the border.