Podrias crear dos selecciones en la primera SELECT categoria FROM descargas y la otra lo mismo SELECT id FROM descargas_cat, aqui hay un ejemplo un poquitin mas completo:
$result = mysql_query("SELECT categoria, nombre FROM descargas");
$result2 = mysql_query("SELECT id FROM descargas_cat");
while ($row = mysql_fetch_array($result, $result2)) {
echo "<a href=bajar.php?id=".$row["id"]."&categoria=".$row[categoria].">".$row["nombre"]."</a>";
No le he probado solo lo he creado sobre la marcha, intentalo, salu2