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\sim$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 $\sim$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\pm2.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 upward 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.