I found a solution in a blog post:
With GhostScript (and Windows users can access gs via cygwin), you can do it with the following command:
gs \
-sOutputFile=grayscale.pdf \
-sDEVICE=pdfwrite \
-sColorConversionStrategy=Gray \
-dProcessColorModel=/DeviceGray \
-dCompatibilityLevel=1.4 \
source.pdf
This will convert source.pdf to grayscale.pdf and put you into a GhostScript shell. To exit, press return and then enter quit in the shell.
Page 1
>>showpage, press <return> to continue<<
GS>quit
Alternately, you can pipe null in as input and that will convert the PDF and not leave you in the GhostScript shell.
command < /dev/null
Or, in a Windows command prompt:
command < NUL
Edit: from a comment, an improvement (for this case) in the arguments you can pass:
gs \
-o grayscale.pdf \
-sDEVICE=pdfwrite \
-sColorConversionStrategy=Gray \
-dProcessColorModel=/DeviceGray \
-dCompatibilityLevel=1.4 \
source.pdf
(This will circumvent the need for dealing with the GS prompt.)