Если значение имеет тип string, вы можете просто привести его:
var result = source.Select(x => new KeyValuePair<string,string>(x.key,(string)x.value)
Если значение необходимо преобразовать, вы можете либо использовать .ToString (), как уже предлагалось, либо использовать функцию преобразователя. Возможно, ваш второй объект - это класс Person с свойством First и LastName, и вы хотите получить полное имя в результате:
var result = source.Select(x => new KeyValuePair<string,string>(x.key, string.Format("{0} {1}", ((Person)x.Value).FirstName, ((Person)x.Value).SecondName))
Конечно, вы можете использовать метод, чтобы упростить ваше преобразование
var result = source.Select(Convert);
private KeyValuePair<string,string> Convert(KeyValuePair<string,object> pair)
{
var key = pair.Key;
var person = (Person)pair.Value;
var fullName = string.Format("{0} {1}", person.FirstName, person.LastName);
return new KeyValuePair<string,string>(key, fullName);
}