Bueno, creo q en lo q estás fallando es q la funcion suma no la llamas nunca. Tendría q ser algo como:
<form action"" name="formulario" method="post" id="formulario">
<label>opciones
<select name="select" id="select" onclick="suma()">
<option value="580">opcion a elegir 1</option>
<option value="1300">opcion a elegir 2</option>
<option value="600">opcion a elegir 3</option>
</select>
</label>
<p>
<label> PROVINCIA
<select name="select2" id="select2" onclick="suma()">
<option value="30">Huelva</option>
<option value="20" selected>Sevilla</option>
<option value="30">Cádiz</option>
<option value="30">Córdoba</option>
<option value="30">Málaga</option>
<option value="30">Jaén</option>
<option value="40">Granada</option>
<option value="50">Almería</option>
</select>
</label>
</p>
<p>
<input type="checkbox" name="select3" id="select3" value="1000" onclick="suma()">
</p>
<p>
<label>
<input type="submit" name="Submit" value="Obtener presupuesto">
</label>
<input name="valor3" type="text" id="valor3">
</p>
</form>
y creo q en vez de poner un input como valor3, deberías poner alguna etiqueta o un text pero bloqueado para q ese valor no se modifique por el usuario. Salu2