Supposed that your run the program in CUI by typing xine-ui. The following command will show you where it is installed.
$ which xine-ui
Remember the path. Then, on KDE desktop, right-click to show the menu.
Select "Create New" -> "Link to Application". On the "General" tab, type in the name of the shortcut and click on the icon to select an icon. Then go to the "Execute" tab, type the path of the program into the "Command" box. Click "Ok" and you are done!