É 100% possível. Você só precisa abrir Startup Applications e adicionar um novo programa de inicialização. O comando será algo como wine "/home/$user/.wine/drive_c/Program Files/you/program.exe"
Substitua $user
pelo seu nome de usuário.
Por exemplo, se eu quisesse executar o IE na inicialização, seria algo como: wine "/home/dakota/.wine/drive_c/Program Files/Internet Explorer/iexplore.exe"
Lembre-se de manter as aspas no comando ou ele não funcionará.