Can a E5 and E4 from same company go on vacation together and bring their significant other, or is that fraternization?

AR 600-20 has the answers:
4–14. Relationships between Soldiers of different grade

a. The term "officer" used in this paragraph includes both commissioned and WOs unless otherwise stated. The term “noncommissioned officer” refers to a Soldier in the grade of corporal to command sergeant major/sergeant major. The term “junior enlisted Soldier” refers to a Soldier in the grade of private to specialist. The provisions of this paragraph apply to both relationships between Soldiers in the Active and Reserve Components and between Soldiers and personnel of other military Services. This policy is effective immediately, except where noted below, and applies to opposite-gender relationships and same-gender relationships.
b. Soldiers of different grades must be cognizant that their interactions do not create an actual or clearly predictable perception of undue familiarity between an officer and an enlisted Soldier, or between an NCO and a junior-enlisted Soldier. Examples of familiarity between Soldiers that may become “undue” can include repeated visits to bars, nightclubs, eating establishments, or homes between an officer and an enlisted Soldier, or an NCO and a junior-enlisted Soldier, except for social gatherings, that involve an entire unit, office, or work section. All relationships between Soldiers of different grade are prohibited if they—
(1) Compromise, or appear to compromise, the integrity of supervisory authority or the chain of command.
(2) Cause actual or perceived partiality or unfairness.
(3) Involve, or appear to involve, the improper use of grade or position for personal gain.
(4) Are, or are perceived to be, exploitative or coercive in nature.
(5) Create an actual or clearly predictable adverse impact on discipline, authority, morale, or the ability of the command to accomplish its mission.
c. Certain types of personal relationships between officers and enlisted Soldiers, or NCOs and junior enlisted Soldiers, are prohibited. Prohibited relationships include the following:
(1) Ongoing business relationships between officers and enlisted personnel, or NCOs and junior enlisted Soldiers. This prohibition does not apply to landlord/tenant relationships or to one-time transactions such as the sale of an automobile or house, but does apply to borrowing or lending money, commercial solicitation, and any other type of ongoing financial or business relationship. Business relationships between NCOs and junior enlisted Soldiers that exist at the time this policy becomes effective and that were authorized under previously existing rules and regulations, are exempt provided the individuals are not in the same unit or chain of command and the relationship does not meet the criteria listed in paragraph 4–14b(1 through 5). In the case of ARNG or U.S. Army Reserve personnel, this prohibition does not apply to relationships that exist due to their civilian occupation or employment.
(2) Dating, shared living accommodations other than those directed by operational requirements, and intimate or sexual relationships between officers and enlisted personnel, or NCOs and junior enlisted Soldiers. This prohibition does not apply to the following:
(a) When evidence of fraternization between an officer and enlisted member or an NCO and a junior enlisted Soldier prior to their marriage exists, their marriage does not preclude appropriate command action based on the prior fraternization. Commanders have a wide range of responses available including counseling, reprimand, order to cease, reassignment, administrative action, or adverse action. Commanders must carefully consider all of the facts and circumstances in reaching a disposition that is appropriate. Generally, the commander should take the minimum action necessary to ensure that the needs of good order and discipline are satisfied.
(b) Situations in which a relationship that complies with this policy would move into noncompliance due to a change in status of one of the members (for instance, a case where two junior enlisted members are dating and one is subsequently commissioned or selected to be a WO, commissioned officer, or NCO). In relationships where one of the enlisted members has entered into a program intended to result in a change in his or her status from enlisted to officer or junior enlisted Soldier to NCO, the couple must terminate the relationship permanently or marry within one year of the date of the appointment or the change in status occurs.

Based only on what you’ve written, it would seem to set up a possible fraternization issue, especially since you’re both in the same platoon. Before making plans, consult your chain-of-command and possibly the JAG for a better read.

If you are USAR/ARNG and your relationship exists due to an outside association you should be good. Never a bad idea to consult the JAG or the IG. They both can advise on whether it’d be an issue.