We present Hubble Space Telescope optical and near-IR transmission spectra of the transiting hot-Jupiter WASP-31b. The spectrum covers 0.3-1.7 {mu}m at a resolution R~70, which we combine with Spitzer photometry to cover the full-optical to IR. The spectrum is dominated by a cloud deck with a flat transmission spectrum which is apparent at wavelengths >0.52{mu}m. The cloud deck is present at high altitudes and low pressures, as it covers the majority of the expected optical Na line and near-IR H_2_O features. While Na I absorption is not clearly identified, the resulting spectrum does show a very strong potassium feature detected at the 4.2{sigma} confidence level. Broadened alkali wings are not detected, indicating pressures below ~10 mbar. The lack of Na and strong K is the first indication of a sub-solar Na/K abundance ratio in a planetary atmosphere (ln[Na/K]=-3.3+/-2.8), which could potentially be explained by Na condensation on the planet's night side, or primordial abundance variations. A strong Rayleigh scattering signature is detected at short wavelengths, with a 4{sigma} significant slope. Two distinct aerosol size populations can explain the spectra, with a smaller sub-micron size grain population reaching high altitudes producing a blue Rayleigh scattering signature on top of a larger, lower lying population responsible for the flat cloud deck at longer wavelengths. We estimate that the atmospheric circulation is sufficiently strong to mix micron size particles upwards to the required 1-10 mbar pressures, necessary to explain the cloud deck. These results further confirm the importance of clouds in hot Jupiters, which can potentially dominate the overall spectra and may alter the abundances of key gaseous species.