Excelで、Ctrl+Spaceキーは列全体を選択するショートカットで便利なので普段から多用しています。

回答受付中なのに、回答記入欄がありませんので　コメントにします。
原因はわかりませんが（キーボードの接触不良化かごみ）キ－ボードを掃除すれば直ることはよくあります。
同じ操作は簡単にできます、表の上に並んだA,B,C,・・・をクリックすれば列全体が選択できます。また、Shift+Spaceは表の１，２，３・・・をクリックすれば行全体を選択できます。

ハード不良とか単純な問題ではありません。
スペースキー単体、Ctrlキー単体や、Ctrl+[Space以外]や、[Ctrl以外]+Spaceの組み合わせは正常に動作します。
Ctrl+Spaceだけが利かないことやExcelを再起動すれば直ることから、何かソフト的な原因に起因すると思われます。
マウスでの列選択（A,B,C,・・・をクリック）ができることは質問に記載済みです。

確証は無いのでコメント欄にて。

なんらかのキーボードフックを行っている常駐アプリとバッティングしているのでは？と思います。
Visual Studio 等をお持ちであれば「Spy++」でキーボードメッセージをトレースすることが可能です。

WM_KEYDOWN nVirtKey:VK_CONTROL
WM_KEYDOWN nVirtKey:VK_SPACE

出力されたメッセージのプロパティにて [ウインドウハンドル] - [プロセス] をたどって、
Excel 以外のプロセスID だった場合、そのプロセスがキーボードフックしている可能性があります。
Excel だった場合は、すみません。

キーボードフックしているとspy++がそういう挙動になるのでしょうか？ メッセージと言うよりウィンドウハンドルに結びついているものですので、GetWindowThreadProcessIdで取れる値（ウィンドウを作成したプロセスID＝つまりExcel以外が返ってくる事は無い）のように思えるのですが．．．

キーボードフックを行うような常駐アプリは基本的に入れないし、また勝手に入らないように気をつけているので無いとは思いますが、一応今度発生したら試してみます。
ただExcelの再起動で復旧するので、Excel自体の不具合か、または何か知らない機能がONになってしまった等の可能性が高いと考えています。

spy++もめんどいなぁと考えていたらなんだか自力でデバッガを使って追いかける方法もあるなと思い至りました。。そこまで暇があればですけど。

キーボードフックに詳しいわけではないので、説明が間違っていたらすみません。

>キーボードフックしているとspy++がそういう挙動になるのでしょうか？

省略して書いてしまいましたが、実際に、常駐アプリによってフックされている場合、
Spy++ で出力されるウィンドウハンドルは Excel ではなく常駐アプリのものになります。

例えば、Excel のウィンドウハンドルが 0000AAAA、常駐アプリのウィンドウハンドルが 0000BBBB で、
常駐アプリによって [Ctrl] キーメッセージがフックされているとすると、

0x0000AAAA WM_KEYDOWN nVirtKey:VK_SHIFT
0x0000AAAA WM_KEYDOWN nVirtKey:VK_SPACE
0x0000BBBB WM_KEYDOWN nVirtKey:VK_CONTROL
0x0000AAAA WM_KEYDOWN nVirtKey:VK_SPACE

のように出力されます。

フックされていないとしたら、

0x0000AAAA WM_KEYDOWN nVirtKey:VK_SHIFT
0x0000AAAA WM_KEYDOWN nVirtKey:VK_SPACE
0x0000AAAA WM_KEYDOWN nVirtKey:VK_CONTROL
0x0000AAAA WM_KEYDOWN nVirtKey:VK_SPACE

のように出力されるかと思います。

もし、Excel でメッセージが処理されていて、キーが効かないのでしたら、Excel の問題な気がします。
Spy++ で解決に至らないかもしれませんが、問題の切り分けには使えるかと思います（原因が Excel なのか常駐アプリなのか）

自分も、過去にファンクションキーか何かが効かなくなったことがあって、
そのとき Spy++ で調べて、別アプリケーションが悪さをしている（バッティングしている）
ということがありましたので、似たような事象なのでは？と思い、コメントしました。

これってまだ未解決ですか？
私もたまになります。
気づいたらなってるし気づいたら直ってますのであまり気にしてませんでしたが。

なんか、日本語入力と英語入力を切り替えたりすると直った気がします。こんな単純な問題じゃないかもしれませんが。

参考までに。