-Should the queue tracks also be shuffled if you press shuffle?
No. Personally, I build a queue to listen to songs in that particular order. Otherwise it would just be a playlist.

-Should the tracks end up at the end of the queue?
Yes.

-Should the queued tracks stay in the queue once they were played back?
No.

-Anything else?
Maybe add a 'Current Playback Queue' item to the main application page? I mean the one that you see directly after starting CuteSpot, with Inbox, Starred, etc. Perhaps the queue item could be placed directly below 'Inbox'? For me it would be the obvious place, and the older Spotify Desktop application also had that option (they removed it now, no idea why, annoyed me anyway )
I also like the idea of the queue being persistant over applications shutdowns