私の環境(Ubuntu 17.10)では以下の手順でDockから起動できるようになりました。

1. KSudokuをインストール
sudo apt install ksudoku

2. KSudokuの.desktopファイルを修正
sudo sed -i s/'Exec=ksudoku %i -qwindowtitle %c'/'Exec=ksudoku'/g /usr/share/applications/kde4/org.kde.ksudoku.desktop

3. アクティビティでKSudokuを検索、表示されたアイコンを右クリック → お気に入りに追加

shermansweet による投稿:

四角のアイコンをもともとの数独の絵柄に直すにはどうしたら良いでしょうか？

一旦alacarteで編集した.desktopファイル（恐らく ~/.local/share/applications/ にあるはず）を削除した後、上記のように実行してみてはいかがでしょうか。

（ただ、KSudokuを起動するとDockのアイコンが二重に表示されますけど…）

DockにKSudokuを登録して正常に起動できるようにする手順のまとめです。

1.KSudokuを再インストール
sudo apt install --reinstall ksudoku

2. ~/.local/share/applications/ 以下に alacarte や menulibre で弄った .desktop ファイルがあるなら削除。

3. KSudokuの.desktopファイルを修正

sudo sed -i s/'Exec=ksudoku %i -qwindowtitle %c'/'Exec=ksudoku'/g /usr/share/applications/kde4/org.kde.ksudoku.desktop

または

sudo gedit /usr/share/applications/kde4/org.kde.ksudoku.desktop
修正前：Exec=ksudoku %i -qwindowtitle %c
修正後：Exec=ksudoku

4. アクティビティでKSudokuを検索、表示されたアイコンを右クリック → お気に入りに追加

ご回答ありがとうございます。
17.10でコマンドでしかKSudokuが起動しない で、解決策を提示していただきました。

/usr/share/applications/kde4/org.kde.ksudoku.desktop

yutarine による投稿:

Execのところのksudokuに付いているオプションを外した.desktopファイルを作って試してみたところ、KSudokuを実行することが出来ました。
一時的な対処方法としては、KSudokuの.desktopファイルを修正すればよさそうです。
オリジナルの.desktopファイルをいじるのではなく、それをコピーしてきて
ユーザー環境にカスタマイズした.desktopファイルを置いて利用するのがいいかと思います。

私の理解不足で、Exec=ksudoku %i -qwindowtitle %cすべてをを削除してしまったのでKsudokuは起動するが
アイコンが変わってしまったと思われます。

ご指示のように
2. ~/.local/share/applications/ 以下に alacarte や menulibre で弄った .desktop ファイルがあるなら削除。
しまして
:~/.local/share/applications$ ls
alacarte-made-1.desktop
alacarte-made.desktop
emacs.desktop
mimeapps.list
の
alacarte-made-1.desktop
alacarte-made.desktop
を削除しました。
この時点でDockに登録されていた四角のアイコンと、もともとの数独の絵柄のアイコンが削除された「ようです」
気がついたら削除されていました。（この２つのファイルで良かったのかなという気がします）

3. KSudokuの.desktopファイルを修正
4. アクティビティでKSudokuを検索、表示されたアイコンを右クリック → お気に入りに追加
を行いましたところもともとの数独の絵柄のアイコンがDockに登録され、クリックで正常に起動できました。

確認のため
:~/.local/share/applications$ ls
したところ以下のように
emacs.desktop
kde4-org.kde.ksudoku.desktop
mimeapps.list

kde4-org.kde.ksudoku.desktopができており、/usr/share/applications/org.kde.ksudoku.desktopと
同じでした。

丁寧に手順のまとめまで書いていただきありがとうございました。