Hello

Ok, here is what i suggest. When you work on something in Photoshop work in RGB mode and make sure that all Adobe applications uses same working color space which can be set from the Bridge.
Then that Photoshop made file by all means you can save as native psd (it can be layered) format since Illustrator recognizes perfectly psd file and you can do place in Illustrator. What is great thing in Illustrator that bellow Main menu in Control palette you can see data for your placed psd image for example which color space of the document is, what resolutions and most importantly to embed that image. You will embed that psd file when you are completely sure that you are done working on it and you are ready to make pre press file. Next thing is why you have used RGB color space in Photoshop is because that is better for editing instead of CMYK and before you embed that file in Illustrator you will use Edit Original function from Control palette and convert to working CMYK and on fly you will be back in Illustrator where you will be notified that linked file was changed or missing but the part you are interested is that your file is now in CMYK mode and also make sure that is 300ppi too before embedding in Illustrator and make sure that Illustrator document initially was opened as CMYK document.
Concerning printer and ICC profile it would be the best if they can give you ICC profile of theirs machine with ink+paper combination that your design will be printed on where even in Illustrator you can simulate device or "soft proof the document and to see do you like the appearance of it... If not you can always make changes till you get satisfactory result.
I hope this was helpful and if any questions... you know... shoot

Cheers
